픽셔너리

우주의 아직 발견되지 않은 곳에 수학자만 사는 나라가 있는 행성이 있다. 이 나라에는 수학자가 $N$명 살고, 수학자마다 자기만의 도시에 산다. 도시에는 $1$번부터 $N$번까지 번호가 붙어 있다. 수학자는 온라인으로 이야기하거나 서로의 논문을 읽으며 지내서, 처음에는 어느 두 도시도 도로로 이어져 있지 않다.

그러던 어느 날 한 수학자가 스마트폰으로 논문을 쓰다가 자동 고침이 "자명하다"를 "픽셔너리"로 바꿔 버렸고, 논문은 그대로 출판됐다. 곧 온 나라가 픽셔너리를 알게 되어 모여서 게임을 하고 싶어했고, 도시를 잇는 도로 공사가 시작됐다.

공사는 모두 $M$일 동안 다음 일정으로 진행된다. 첫째 날에는 최대공약수가 $M$인 모든 도시 쌍 사이에 도로를 놓는다. 둘째 날에는 최대공약수가 $M-1$인 모든 도시 쌍 사이에 도로를 놓고, 이렇게 계속해서 $M$일째에는 서로소인 모든 도시 쌍 사이에 도로를 놓는다. 정리하면 $i$일째에는 $\gcd(a, b) = M - i + 1$인 두 도시 $a$와 $b$ 사이에 도로를 놓는다.

두 수학자는 사는 도시 사이를 도로를 따라 오갈 수 있게 되면 만날 수 있고, 중간에 다른 도시를 거쳐도 된다. 수학자들은 공사로 바빠서, 주어진 두 수학자가 함께 픽셔너리를 할 수 있게 되기까지 걸리는 최소 일수를 대신 구해 달라고 부탁했다.

첫째 줄에 양의 정수 $N$, $M$, $Q$가 주어진다. ($1 \le N, Q \le 100\,000$, $1 \le M \le N$) 차례대로 도시의 수, 도로 공사에 걸리는 날수, 질의의 수다.

다음 $Q$개의 줄에는 서로 다른 두 양의 정수 $A$와 $B$가 주어진다. ($1 \le A, B \le N$) 함께 픽셔너리를 하기까지 며칠이 걸리는지 알고 싶어하는 두 수학자가 사는 도시다.

$Q$개의 줄을 출력한다. $i$번째 줄에는 $i$번째 질의의 두 수학자가 함께 픽셔너리를 할 수 있게 되기까지 걸리는 최소 일수를 출력한다.

첫 번째 예제 설명이다. 첫째 날에 도로 $(3, 6)$이 놓이므로 두 번째 질의의 답은 $1$이다. 둘째 날에는 도로 $(2, 4)$, $(2, 6)$, $(2, 8)$, $(4, 6)$, $(6, 8)$이 놓이고, 도시 $6$을 거쳐 도시 $4$와 도시 $8$이 이어진다. 셋째 날에는 서로소인 도시 사이에 도로가 놓이므로 도시 $2$와 도시 $5$가 이어진다.

두 번째 예제 설명이다. 둘째 날에 도로 $(20, 15)$가 놓이고, 넷째 날에 도로 $(15, 9)$가 놓인다. 넷째 날이 지나면 도시 $15$를 거쳐 도시 $20$과 도시 $9$가 이어진다.