Problem D
Chewbacca

You are given a tree of out-degree $K$ with $N$ nodes or, in other words, each node can have at most $K$ children. The tree is constructed so it is of the “lowest energy”: the nodes are placed in a new depth of the tree only when all the places (from left to right) in the previous depth have been filled. This is also the order of enumerating the nodes, starting with 1. Picture 1 depicts an example of a tree of order $3$ with $9$ nodes.

Figure 1: Sample Input 2

You need to output answers to $Q$ queries in the form of $x$ $y$, where the answer is the minimal number of steps needed to get from node $x$ to node $y$.

Input

The first line of input contains the integers $N$ ($1 \leq N \leq 10^{15} $), $K$ ($1 \leq K \leq 1\, 000$) and $Q$ ($1 \leq Q \leq 100\, 000$) from the task. Each of the following $Q$ lines contains pairs $x$ $y$ ($1 \leq x, y \leq N$, $x \neq y$) from the task.

Output

Output $Q$ lines, each line containing the answer to a query from the task.

7 2 3
1 2
2 1
4 7

1
1
4

9 3 3
8 9
5 7
8 4

2
2
3