Mining

Problem Background

ZY, ZHB, JGY, and Little Luo Xiang have obtained enough food by planting wheat and raising cows in my world. They realize it's time to embark on an underground journey.

Problem Description

They have discovered $n$ caves, marked with natural numbers from 1 to $n$, and each cave can be connected to at most $q$ other caves (forming a complete $q$-ary tree, as shown in the figure below). They are scattered in different caves and want to know how many caves they need to pass through when they exchange resources.

Explanation: The circles in the figure represent caves, the straight lines represent tunnels, and the numbers inside the circles are cave numbers.

Input Format

The first line consists of three integers $n, q, k$, representing the number of caves, the maximum number of caves each cave can be connected to, and the number of queries.

The next $k$ lines (from the 2nd to $k+1$) each contain two integers $x, y$, representing the caves where two people are located.

Output Format

$k$ lines, each containing an integer, representing the answers to the queries.

Example #1

10 3 3
1 1
4 5
1 4

0
3
1

10 5 1
9 6

3

10 1 3
4 2
2 7
10 3

2
5
7

Example Explanation

Example 1

Query 1: No need to pass through any caves.

Query 2: 4 -> 1 -> 2 -> 5, passing through three caves.

Query 3: 1 -> 4, passing through one cave.

Hint

• For 5% of the data, $1\le n, q\le 10^2$, $1\le k\le 5$;
• For 100% of the data, $1\le n, q\le 10^6$, $1\le k\le 10^5$.

Finding the pattern

The data is very permissive; once you find the pattern, you don't need to worry about time complexity.