给你一棵 $K$ 叉树，它有 $N$ 个节点。换句话说，每个节点最多可以有 $K$ 个子节点。这棵树的构建方式使其具有“最低能量”：只有当上一深度的所有位置（从左到右）都被填满时，节点才会放置在树的新深度中。这也是节点编号的顺序，从 $1$ 开始。下图展示了一个包含 $9$ 个节点的 $3$ 叉树的例子。

你需要输出对 $Q$ 次查询的回答，每次查询给出 $x$ 和 $y$，你需要求出从节点 $x$ 到节点 $y$ 所需的最少步数。

输入格式

第一行包含三个整数 $N$ ($1 \le N \le 10^{15}$)、$K$ ($1 \le K \le 1000$) 和 $Q$ ($1 \le Q \le 100\,000$)。

接下来的 $Q$ 行，每行包含一对整数 $x, y$ ($1 \le x, y \le N, x \neq y$)。

输出格式

输出 $Q$ 行，每行包含一个查询的答案。

子任务

• 对于 $20\%$ 的测试数据，满足 $1 \le N, Q \le 1000$。
• 对于 $50\%$ 的测试数据，满足 $1 \le N, Q \le 100\,000$。

样例

输入样例 1

7 2 3
1 2
2 1
4 7

输出样例 1

1
1
4

输入样例 2

9 3 3
8 9
5 7
8 4

输出样例 2

2
2
3

说明

样例 1 说明：给你一棵完全二叉树。节点 $2$ 是节点 $1$ 的直接子节点，因此它们之间的距离正好是 $1$。节点 $4$ 和 $7$ 位于树的完全相反的两侧，因此它们之间的距离是 $4$：$4 \to 2 \to 1 \to 3 \to 7$。

样例 2 说明：该样例对应于图中的树。