Что ж, вот еще одна математическая задача. Как известно, НОД — наибольший общий делитель. Найти НОД двух положительных целых чисел несложно.
Общий делитель двух положительных чисел — это число на которое делятся оба этих числа.
Но Вам дана более сложная задача. Требуется найти наибольший общий делитель d двух целых чисел a и b, принадлежащий отрезку целых чисел [low, high] (low ≤ high), то есть такой, что low ≤ d ≤ high.
Может получиться, что в заданном отрезке нет общих делителей.
Даны два целых числа a и b, далее следует n запросов. Каждый запрос — это некоторый отрезок [low, high]. Напишите программу, которая обработает все заданные запросы.
Выходные данные
Выведите n строк, i-ая из них должна содержать ответ на i-ый запрос из входных данных. Если в данном отрезке общих делителей нет, выводите -1 в качестве ответа на запрос.