E. Шарады

В $N$ городах живут математики. Дороги строятся $M$ дней: в $i$-й день соединяются все пары городов $A$ и $B$, у которых $\gcd(A, B) = M + 1 - i$. Для каждого запроса определите, через сколько дней от начала строительства данная пара сможет встретиться, доехав по уже построенным дорогам.

В первой строке $N$, $M$ и $Q$ ($1 \le N, Q \le 100\,000$, $1 \le M \le N$). В каждой из следующих $Q$ строк — числа $A$ и $B$ ($1 \le A, B \le N$).

Для каждого запроса выведите номер дня в отдельной строке.