Pictionary

In an undiscovered corner of the universe there is a planet with a country where only mathematicians live. The country has $N$ mathematicians, and each one lives in a city of their own. The cities are numbered $1$ to $N$. Mathematicians talk online or read each other's papers, so at the start no two cities are connected by a road.

Life was fine until one mathematician wrote a paper on a smartphone. Autocorrect changed the word "self-evident" to "Pictionary", and the paper was published that way. The whole country soon heard about Pictionary and wanted to meet and play, so construction of roads between the cities began.

The construction lasts $M$ days and follows this schedule. On the first day, roads are built between every pair of cities whose greatest common divisor is $M$. On the second day, roads are built between every pair whose greatest common divisor is $M-1$, and so on, until day $M$, when roads are built between every pair of coprime cities. Formally, on day $i$ a road is built between cities $a$ and $b$ if $\gcd(a, b) = M - i + 1$.

Two mathematicians can meet once their cities can reach each other along roads, passing through other cities if needed. The mathematicians are busy with the construction, so they ask you for the minimum number of days after which a given pair can play Pictionary together.

The first line contains three positive integers $N$, $M$, and $Q$ ($1 \le N, Q \le 100\,000$, $1 \le M \le N$): the number of cities, the number of days the construction takes, and the number of queries.

Each of the next $Q$ lines contains two distinct positive integers $A$ and $B$ ($1 \le A, B \le N$), the cities of the two mathematicians who want to know how many days it takes before they can play Pictionary together.

Print $Q$ lines. Line $i$ contains the minimum number of days after which the two mathematicians of query $i$ can play Pictionary together.

Explanation of the first sample. On day $1$ the road $(3, 6)$ is built, so the answer to the second query is $1$. On day $2$ the roads $(2, 4)$, $(2, 6)$, $(2, 8)$, $(4, 6)$, and $(6, 8)$ are built, and cities $4$ and $8$ become connected through city $6$. On day $3$ roads are built between coprime cities, so cities $2$ and $5$ become connected.

Explanation of the second sample. The road $(20, 15)$ is built on day $2$ and the road $(15, 9)$ on day $4$. After day $4$, cities $20$ and $9$ are connected through city $15$.