This is a question from my computer science class and was wondering if I could get some help on it. How would this problem be solved in Java ? Thanks!

Flavius Josephus was part of a Jewish rebellion against the Romans in the first century. His group was surrounded and placed under a siege. The Jewish men did not want to be captured and dies under the hand of the Romans, so they agreed to kill each other. The details of their method are unclear, nut the method that has been repeated most frequently is that the men stood in a circle and counted by three. Every time a reached the number three, he was killed by the previous man in the count. According to Josephus, he escaped because he ended up being one of the last two men who both agreed not to kill each other.

Your task is to help Josephus survive. The actual number of men in the group (n) is unknown. The number counted to (k) before the next man is killed is also unknown. As a result, you must be able to compute where Josephus should stand in the circle so that his is the last man to survive for all combinations of n and k. The man in the circle are numbered clockwise from 1 to n with the first person counting as 1.

Input

The input to the program will consist of a series of l lines describing the configuration of men. The first line contains an integer l. The remaining l lines contain two integers, n and k respectively. The range of legal input values are: 0 < k <= n < 1,000,000.

Output

For each pair of values n and k, you will produce one line of output. The output should be the location in the circle that Josephus should stand in order to be spared.

Sample Input:

10

2 1

2 2

3 1

3 2

3 3

4 1

4 2

4 3

4 4

24389 9832

Sample Output:

2

1

3

3

2

4

1

1

2

21865