Problem Description

In a remote corner of the universe, there exists a planet with a country inhabited solely by mathematicians. In this country, there are \( n \) mathematicians, each living in their own city, with no roads connecting any of them, as they communicate online. The cities are numbered from 1 to \( n \).

One mathematician accidentally published a paper with the word "Pictionary" instead of "self-evident" due to a smartphone autocorrect error. This sparked an interest in Pictionary among the mathematicians, who now want to meet and play together. Consequently, a road construction project was initiated.

The road construction will last for \( m \) days. On the \( i \)-th day, roads will be built between cities \( a \) and \( b \) if \(\gcd(a, b) = m - i + 1\).

Since the mathematicians are busy with construction work, they have asked you to determine the earliest day when a given pair of mathematicians can meet and play Pictionary.

Input Format

The first line contains three positive integers \( n \), \( m \), and \( q \), representing the number of cities, the number of days the road construction lasts, and the number of queries, respectively.

Each of the following \( q \) lines contains two positive integers \( a \) and \( b \), representing a query for the earliest day when the mathematicians from cities \( a \) and \( b \) can meet.

Output Format

For each query, output a single line containing the earliest day when the mathematicians from the corresponding cities can meet.

Notes

Data Range:

• For 40% of the data: \( n \leq 4000 \), \( q \leq 10^5 \)
• For all data: \( 1 \leq n, q \leq 10^5 \), \( 1 \leq m \leq n \)

Sample Input and Output

Sample Input #1

8 3 3
2 5
3 6
4 8

Sample Output #1

3
1
2

Sample Input #2

25 6 1
20 9

Sample Output #2

4

Sample Input #3

9999 2222 2
1025 2405
3154 8949

Sample Output #3

1980
2160

Explanation of Sample Cases

Clarification of the first test case:

• On the first day, road (3, 6) is built. Therefore, the answer to the second query is 1.
• On the second day, roads (2, 4), (2, 6), (2, 8), (4, 6), and (6, 8) are built. Cities 4 and 8 are now connected via city 6.
• On the third day, roads between relatively prime cities are built, so cities 2 and 5 are connected.

Clarification of the second test case:

• On the second day, road (20, 15) is built, whereas on the fourth day, road (15, 9) is built. After the fourth day, cities 20 and 9 are connected via city 15.

见题面 Input 部分

见题面 Output 部分