C. Coin
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output
The government decided to cut the navy's budget and distribute the saved gold directly to the pirates. This managed to eliminate more pirates than the navy ever did.
—Boiled-chicken

The pirates have just seized a giant gold coin!

To determine the ownership of this gold coin, they decided to select the owner using the following method:

Let the current number of remaining pirates be $$$n$$$. The pirates line up in a queue, and the pirates at positions $$$1, 1+k, 1+2k, \dots, 1+(\lceil\frac{n}{k}\rceil - 1) k$$$ are eliminated. This operation is repeated until only one pirate remains. The final remaining pirate will receive the gold coin.

Charlie is the smartest among the pirates. He wants to know where he should stand initially to be the last pirate remaining and win the coin.

Input

Each test file contains multiple test cases. The first line contains the number of test cases $$$T$$$ ($$$1 \leq T \leq 100$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$2 \leq n, k \leq 10^{12}$$$), representing the initial number of pirates and the parameter used for elimination.

For each test file, it is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^{12}$$$, and the sum of $$$k$$$ over all test cases does not exceed $$$10^{12}$$$.

Output

For each test case, output a single integer on a new line, indicating the position of the pirate who will ultimately receive the gold coin in the initial queue.

Example
Input
4
6 2
8 3
10000 2
1919810 114514
Output
4
8
8192
1919805
Note

For the first test case in the example, the positions of the remaining pirates in the original sequence after each round are:

  • Initial state: $$$1, 2, 3, 4, 5, 6$$$.
  • After the first round: $$$2, 4, 6$$$.
  • After the second round: $$$4$$$.

For the second test case in the example, the positions of the remaining pirates in the original sequence after each round are:

  • Initial state: $$$1, 2, 3, 4, 5, 6, 7, 8$$$.
  • After the first round: $$$2, 3, 5, 6, 8$$$.
  • After the second round: $$$3, 5, 8$$$.
  • After the third round: $$$5, 8$$$.
  • After the fourth round: $$$8$$$.