K-ary Tree

Interview

Time limit1sMemory limit256 MB

Summary

Compute the edge distance for each query pair in a complete K-ary tree with N nodes numbered in breadth-first order.

Level: Medium5 of 10
Topics: Tree, Math
Solved: No attempts yet

Problem

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.

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.

Input

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$ )

Output

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

Examples2

Example 1
Input
```
7 2 3
1 2
2 1
4 7
```
Expected output
```
1
1
4
```
Example 2
Input
```
9 3 3
8 9
5 7
8 4
```
Expected output
```
2
2
3
```