题目描述

一棵 $n$ 个节点的 $k$ 级树是按照如下方式构造出来的：

• 首先，新建根节点，并将其编号为 $1$。
• 随后重复如下步骤直至节点总数恰好为 $n$：
  • 设上一个新增节点的编号为 $x$。
  • 在上一层中从左往右找到第一个儿子个数<k 的节点。
    • 如果该节点上没有儿子，则在该节点下新增一个儿子节点，编号为 $x+1$，并在点 $x+1$ 和我们找到的该父亲节点之间连一条长度为 $1$ 的边。
    • 否则，在该节点最近添加的儿子节点的右边新增一个儿子节点，编号为 $x+1$，并在点 $x+1$ 和我们找到的该父亲节点之间连一条长度为 $1$ 的边。
  • 如果在当前层没有找到儿子个数 <k 的节点，则跳到下一层。

例如，下图为按照如上方法构造出来的包含 $9$ 个节点的 $3$ 级树：

现在，你得到了这棵包含 $n$ 个节点的 $k$ 级树，你需要回答 $q$ 次询问。每次询问给定两个整数 $x,y$，你需要回答在该树中节点 $x$ 到节点 $y$ 的最短路径长度。

输入格式

第一行输入三个整数 $n,k,q$，分别表示树的节点数、级数和询问次数。
随后 $q$ 行，每行输入两个整数 $x,y$，表示本次询问的两个节点。

输出格式

输出 $q$ 行，每行一个整数，表示节点 $x$ 到节点 $y$ 的最短路径长度。

输入输出样例 #1

输入 #1

7 2 3
1 2
2 1
4 7

输出 #1

1
1
4

输入输出样例 #2

输入 #2

9 3 3
8 9
5 7
8 4

输出 #2

2
2
3

说明/提示

【样例 1 解释】

下图是样例 1 中构造出来的树：

不难发现，对于第 $1$、$2$ 次询问，由于节点 $2$ 是节点 $1$ 的儿子节点，因此这两个点之间的最短路径长度恰好为 $1$。而对于第 $3$ 次询问，一条最短路径是 $4\rightarrow 2\rightarrow 1\rightarrow 3\rightarrow 7$。因此其最短路径长度为 $4$。

【样例 2 解释】

样例 2 构造出来的树见『题目描述』部分。

【数据范围】

对于 $20\%$ 的数据，保证 $1\leqslant n,q\leqslant 1000$。
对于 $50\%$ 的数据，保证 $1\leqslant n\leqslant 10^5$。
对于所有数据，$1\leqslant n\leqslant 10^{15}$，$1\leqslant k\leqslant 1000$，$1\leqslant q\leqslant 10^5$。

【题目来源】

本题来源自 _COCI 2015-2016 CONTEST 4 T4 CHEWBACCA_，按照原题数据配置，满分 $120$ 分。

由 Eason_AC 翻译整理提供。