K진 트리

각 노드가 자식을 최대 K개까지 가질 수 있는 트리를 K진 트리라고 한다. 노드가 N개인 K진 트리를 다음 규칙으로 만든다. 깊이가 얕은 쪽부터 채우고, 어떤 깊이를 완전히 채우기 전에는 새로운 깊이를 만들지 않는다. 같은 깊이 안에서는 가장 왼쪽부터 차례대로 노드를 붙인다.

노드에는 1번부터 N번까지 번호가 붙어 있다. 깊이가 작은 노드가 먼저 번호를 받고, 깊이가 같으면 왼쪽에 있는 노드가 먼저 받는다. 따라서 1번이 루트이다.

아래 그림은 노드 9개로 이루어진 3진 트리이다.

두 노드 사이의 거리는 한 노드에서 다른 노드까지 가는 경로에 놓인 간선의 개수이다.

N과 K, 그리고 거리를 구해야 하는 노드 쌍이 주어졌을 때 각 쌍의 거리를 구하는 프로그램을 작성하시오.

첫째 줄에 N ($1 \le N \le 10^{15}$), K ($1 \le K \le 1000$), 거리를 구해야 하는 노드 쌍의 개수 Q ($1 \le Q \le 100000$)가 공백으로 구분되어 주어진다.

다음 Q개 줄에는 거리를 구해야 하는 두 노드 x와 y가 주어진다. ($1 \le x, y \le N$, $x \ne y$)

Q개 줄을 출력한다. $i$번째 줄에는 $i$번째로 주어진 두 노드 사이의 거리를 출력한다.