Shortest Path in a K-Level Tree

We are given an integer (n) and a positive integer (k) along with a special tree construction method: a (k)-level tree with (n) nodes is built as follows:

1. Create the root node and label it as (1).
2. Then, repeatedly until there are exactly (n) nodes:
   • Let the last inserted node have label (x).
   • In the previous level (i.e. the level of the parent nodes), scan from left to right to find the first node that has fewer than (k) children.
     • If that node has no child, add a new child with label (x+1) and connect it with an edge of length (1).
     • Otherwise, add a new child to that node (to the right of its most recently added child) with label (x+1) and connect it with an edge of length (1).
   • If no node in that level has fewer than (k) children, then move to the next level.

In other words, the tree is constructed in level order so that for any node (i \gt 1), its parent is given by (\text{parent}(i) = \left\lfloor\frac{i-2}{k}\right\rfloor + 1). (Note that when (k=1), the tree degenerates into a chain with (\text{parent}(i)=i-1).)

After constructing the tree, you are given (q) queries. Each query consists of two integers (x) and (y) and your task is to determine the length of the shortest path from node (x) to node (y). The distance between any two directly connected nodes is (1).

inputFormat

The first line contains three integers \(n\), \(k\) and \(q\) — the number of nodes in the tree, the maximum number of children per node, and the number of queries, respectively.

Each of the following \(q\) lines contains two integers \(x\) and \(y\), representing a query asking for the shortest path length between node \(x\) and node \(y\).

Note: The tree is constructed in level order as described in the problem statement. For every node \(i \gt 1\), its parent is \(\left\lfloor\frac{i-2}{k}\right\rfloor + 1\).

outputFormat

For each query, print a single integer — the length of the shortest path from node \(x\) to node \(y\).

sample

9 3 3
2 3
4 5
8 9

2
3
2