G. Joseph's Puzzle, Again
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Joseph's game is like this: $$$N$$$ people are arranged in a circle clockwise, and each person's number is from $$$1$$$ to $$$N$$$. Starting from No. 1, one person is eliminated by $$$M$$$ people clockwise, leaving the last person as the winner, whose number is the lucky number.

Given $$$N$$$ and $$$M$$$, find the lucky number.

Input

The first line contains one integer $$$T$$$ $$$(1\le T \le 10^4)$$$ — the number of test cases.

For each test case, there are $$$2$$$ integers $$$N$$$ and $$$M$$$ $$$(1\le N \le 10^8, 2\le M\le 10)$$$ in one line.

Output

For each test case, output the lucky number.

Example
Input
3
10 2
10 3
1024 2
Output
5
4
1
Note

Case 1: The elimination order is $$$2, 4, 6, 8, 10, 3, 7, 1, 9$$$, so the lucky number is $$$5$$$.

Case 2: The elimination order is $$$3, 6, 9, 2, 7, 1, 8, 5, 10$$$, so the lucky number is $$$4$$$.