题目描述

有一个 $N$ 个点的完全 $K$ 叉树。

编号从 $1$ 开始，从上到下，从左到右进行编号。

例如，当 $K=3,N=9$ 时，有：

$Q$ 次询问。每次给定 $x,y$。问 $x$ 和 $y$ 号点在树上的最短路径所经过的边数。

输入格式

共 $Q+1$ 行。

第一行三个整数 $N,K,Q$：

接下来 $Q$ 行，每行两个整数 $x,y$，表示一次询问。

输出格式

共 $Q$ 行，第 $i$ 行一个整数，表示每次询问的答案。

输入样例

9 3 3
8 9
5 7
8 4

输出样例

2
2
3

数据范围

对于 $20\%$ 的数据： $1 \le N,Q \le 1000$。

对于 $50\%$ 的数据： $1 \le N,Q \le 10^5$。

对于所有数据：$1\le N \le 10^{15},1\le K \le 1000,1\le Q\le 10^5$，$1\le x,y\le N,x\neq y$。