给定一个由N个节点构成的完全K叉树，节点编号从1到N，按广搜序，即每一个节点最多有K个儿子，且只有当它的上一个节点满K叉后，它才能有儿子。如图所示

现在给你一个Q，和Q个询问。格式如下x y,表示在树上从x号节点到y 号节点要走多少步。
输入：
第一行三个整数N ($1<=N<=10^{15}$), K ($1<=K<= 1 000$) Q ($1<= Q<=100 000$)
接下来Q行，每行一对合法的x,y，$x<>y $ 输出：
Q行，每行一个整数，表示步数。
SCORING
In test cases worth 20% of total points, it will hold 1< =N;Q < =1 000.
In test cases worth 50% of total points, it will hold 1< =N;Q < =100 000.

input
7 2 3
1 2
2 1
4 7
output
1
1
4
input
9 3 3
8 9
5 7
8 4
output 
2
2
3