题目描述

有$\red{n}$个城市，标号为$\red{1}$到$\red{n，}$第$\red{i}$天时，若$\red{gcd(a,b)=m-i+1，}$则标号为$\red{a}$的城市和标号为$\red{b}$的城市会建好一条直接相连的 道路，有多次询问，每次询问某两座城市最早什么时候能联通。

输入格式

第一行输入三个正整数$\red{n,m,q，}$其中$\red{q}$表示询问个数。

接下来$\red{q}$行，每行两个正整数$\red{x，}$$\red{y，}$表示询问城市$\red{x}$和城市$\red{y}$最早什么时候联通。

输出格式

输出$\red{q}$行，每行一个正整数，表示最早联通的天数

样例

输入样例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

提示

数据范围

对于$\red{40\%}$的数据，$\red{1 ≤}$ $\red{n≤}$ $\red{1000}$。

对于$\red{100\%}$的数据，$\red{1 ≤}$ $\red{n,q≤}$ $\red{100000}$。