Build a tree

Problem Description

HazelFan wants to build a rooted tree. The tree has $n$ nodes labeled $0$ to $n-1$, and the father of the node labeled $i$ is the node labeled $\lfloor\frac{i-1}{k}\rfloor$. HazelFan wonders the size of every subtree, and you just need to tell him the XOR value of these answers.

Input

The first line contains a positive integer $T(1\leq T\leq5)$, denoting the number of test cases. For each test case: A single line contains two positive integers $n,k(1\leq n,k\leq10^{18})$.

Output

For each test case: A single line contains a nonnegative integer, denoting the answer.

Sample Input

2

5 2

5 3

Sample Output

7

6

Source

2017 Multi-University Training Contest - Team 7

https://acm.hdu.edu.cn/showproblem.php?pid=6121