Задача №113868. Шарады
В ещё не изведанной части вселенной есть планета, на которой живут одни математики. На этой планете живут N математиков, каждый — в своём городе. Никакие два города не соединены дорогами, потому что математики могут общаться онлайн, оставляя комментарии о научных трудах друг друга.
Всё шло тихо и спокойно, пока один математик не решил написать научную работу со своего мобильного телефона. Автоисправление в телефоне заменило «очевидно» на «шарада». Не перечитав свою работу, математик так и опубликовал её. Совсем скоро об игре в шарады узнали все математики планеты, и им захотелось собраться и поиграть всем вместе. Поэтому в скором времени началась постройка дорог между городами. Строительство дорог будет идти M дней в соответствии со следующим расписанием: в первый день строятся дороги между всеми парами городов, у номеров которых наибольший общий делитель равен M . Во второй день строятся дороги между всеми парами городов, наибольший делитель номеров которых равен M - 1 . И так далее до M -го дня, в который дороги строятся между всеми парами городов с взаимно простыми номерами. Говоря более формально, в i -й день (нумеруя дни с единицы) дороги строятся между всеми такими парами городов A и B , что НОД ( A , B ) = M + 1 - i .
Математики очень заняты постройкой дорог, поэтому они просят вас помочь определить минимальное число дней с начала строительства, через которое данная пара математиков сможет встретиться, чтобы поиграть в шарады.
В первой строке даны три целых целых положительных числа N , M и Q ( 1 ≤ N , Q ≤ 100 000 , 1 ≤ M ≤ N ) - количество городов, длительность строительства дорог и количество запросов соответственно.
В следующих Q строках вводятся по два целых числа A и B ( 1 ≤ A , B ≤ N ) — номера городов двух математиков, которым интересно, через сколько дней они смогут встретиться (добраться из одного город в другой, проехав по уже построенным дорогам).
На каждый из Q запросов выведите ответы — Q чисел, каждое в отдельной строке.
Программы, правильно работающие при N ≤ 1000 , будут оцениваться в 40 баллов.
Пояснение к первому тесту:
В первый день строится дорога (3, 6) . Поэтому ответ на второй запрос 1 . На второй день строятся дороги (2, 4) , (2, 6) , (2, 8) , (4, 6) и (6, 8) . Города 4 и 8 теперь связаны (можно добраться из первого во второй используя город 6 ). На третий день строятся дороги между взаимно простыми городами, поэтому города 2 и 5 оказываются соединены.
Пояснение ко второму тесту:
На второй день строится дорога (20, 15) , на четвертый день — дорога (15, 9) . Таким образом, начиная с четвёртого дня, города, 20 и 9 связаны (через город 15 ).
8 3 3 2 5 3 6 4 8
3 1 2
25 6 1 20 9
4
9999 2222 2 1025 2405 3154 8949
1980 2160