레이팅 미적용There is a planet, in a yet undiscovered part of the universe, with a country inhabited solely
by mathematicians. In this country, there are a total of \(N\) mathematicians, and the interesting
fact is that each mathematician lives in their own city. Is it also interesting that no two cities
are connected with a road, because mathematicians can communicate online or by
reviewing academic papers. Naturally, the cities are labeled with numbers from 1 to \(N\).
Life was perfect until one mathematician decided to write an academic paper on their
smartphone. The smartphone auto-corrected the word “self-evident” to “Pictionary” and the
paper was published as such. Soon after, the entire country discovered pictionary and
wanted to meet up and play, so construction work on roads between cities began shortly.
The road construction will last a total of \(M\) days, according to the following schedule: on the
first day, construction is done on roads between all pairs of cities that have \(M\) as their
greatest common divisor. On the second day, construction is done on roads between all
pairs of cities that have \(M-1\) as their greatest common divisor, and so on until the \(M^{th}\) day
when construction is done on roads between all pairs of cities that are co-prime. More
formally, on the \(i^{th}\) day, construction is done on roads between cities \(a\) and \(b\) if gcd(a, b) = M
- \(i + 1\).
Since the mathematicians are busy with construction work, they’ve asked you to help them
determine the minimal number of days before a given pair of mathematicians can play
pictionary together.
In test cases worth 40% of total points, it will hold \(N \le 1000\), \(Q \le 100\,000\).
The first line of input contains three positive integers N, M and \(Q\) (\(1 \le N\), \(Q \le 100\,000\), \(1 \le M\)
≤\(N\)), the number of cities, the number of days it takes to build the roads, and the number of
queries.
Each of the following \(Q\) lines contains two distinct positive integers \(A\) and \(B\) (\(1 \le A\), \(B \le N\))
that denote the cities of the mathematicians who want to find out the minimal number of days
before they can play pictionary together.
The \(i^{th}\) line must contain the minimal number of days before the mathematicians from the \(i^{th}\)
query can play pictionary together.
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