在宇宙中一个尚未被发现的角落，有一个完全由数学家居住的国家。在这个国家里，总共有 $N$ 位数学家，有趣的是，每位数学家都住在自己独立的城市里。同样有趣的是，起初没有任何两个城市之间有道路相连，因为数学家们可以通过网络或审阅学术论文来进行交流。自然地，这些城市被用 $1$ 到 $N$ 的数字进行了编号。

生活原本是完美的，直到有一位数学家决定在智能手机上写一篇学术论文。智能手机将“显而易见的”（self-evident）这个词自动纠正为了“Pictionary”（画图猜词游戏），而论文也就这样发表了。不久之后，整个国家都发现了 Pictionary 游戏，并希望聚在一起玩，于是城市之间道路的建设工作很快就开始了。

道路建设总共将持续 $M$ 天，具体日程如下：

• 在第一天，在所有最大公约数为 $M$ 的城市对之间修建道路。
• 在第二天，在所有最大公约数为 $M-1$ 的城市对之间修建道路。
• 依此类推，直到第 $M$ 天，在所有互质（最大公约数为 $1$）的城市对之间修建道路。

更正式地，在第 $i$ 天，如果 $\gcd(a, b) = M - i + 1$，则在城市 $a$ 和 $b$ 之间修建道路。

由于数学家们正忙于建设工作，他们请求你帮助他们确定：对于给定的某对数学家，最少需要过去多少天，他们才能聚在一起玩 Pictionary 游戏。

输入格式

输入的第一行包含三个正整数 $N$、$M$ 和 $Q$（$1 \le N, Q \le 100\,000$，$1 \le M \le N$），分别表示城市的数量、修建道路所需的总天数以及询问的数量。

接下来的 $Q$ 行，每行包含两个不同的正整数 $A$ 和 $B$（$1 \le A, B \le N$），表示想要知道最少需要多少天才能聚在一起玩 Pictionary 游戏的两位数学家所在的城市。

输出格式

输出共 $Q$ 行。第 $i$ 行应包含第 $i$ 个询问中两位数学家能够聚在一起玩 Pictionary 游戏所需的最少天数。

子任务

在占总分 40% 的测试数据中，满足 $N \le 1000$，$Q \le 100\,000$。

样例

输入样例 1

8 3 3
2 5
3 6
4 8

输出样例 1

3
1
2

输入样例 2

25 6 1
20 9

输出样例 2

4

输入样例 3

9999 2222 2
1025 2405
3154 8949

输出样例 3

1980
2160

说明

样例 1 解释：

• 在第一天，修建了道路 $(3, 6)$。因此第二个询问的答案是 $1$。
• 在第二天，修建了道路 $(2, 4)$、$(2, 6)$、$(2, 8)$、$(4, 6)$ 和 $(6, 8)$。此时城市 $4$ 和 $8$ 连通了（可以通过城市 $6$ 从一个城市到达另一个城市）。
• 在第三天，修建了互质城市之间的道路，因此城市 $2$ 和 $5$ 连通了。

样例 2 解释：

• 在第二天，修建了道路 $(20, 15)$；在第四天，修建了道路 $(15, 9)$。在第四天之后，城市 $20$ 和 $9$ 通过城市 $15$ 连通。