K-ary Tree

A tree in which every node can have at most K children is called a K-ary tree. A K-ary tree with N nodes is built by the following rule. The shallow depths are filled first, and a new depth is created only after the previous depth is completely filled. Within one depth the nodes are attached from the leftmost position onward.

The nodes are numbered 1 through N. A node at a smaller depth is numbered first, and among nodes at the same depth the leftmost one is numbered first. Node 1 is therefore the root.

The picture below is a 3-ary tree with 9 nodes.

The distance between two nodes is the number of edges on the path from one node to the other.

Given N, K and the node pairs whose distance is asked for, write a program that computes the distance for each pair.

The first line contains N ($1 \le N \le 10^{15}$), K ($1 \le K \le 1000$), and the number of node pairs Q ($1 \le Q \le 100000$), separated by spaces.

Each of the next Q lines contains two nodes x and y whose distance is asked for. ($1 \le x, y \le N$, $x \ne y$)

Print Q lines. On line $i$, print the distance between the two nodes given on the $i$-th query.