Columbia College is choosing one student to be student president, and we need your help!

All of the \(N\) students are standing in a circle, and they count from 1 to \(M\) repeatedly one after another. For example in the beginning, student No.1 counts 1, then student No.2 counts 2, and so on. When a student counts to \(M\), he/she is excluded from the next round. And counting restarts from 1 for the next student in the circle.

Given the number of students \(N\), and number \(M\), your task is to determine who is the last remaining student, which is to be the next president.

For example, with 5 students and \(M=3\),

Student1: 1
Student2: 2
Student3: 3  // Student3 is excluded
Student4: 1
Student5: 2
Student1: 3  // Student1 is excluded
Student2: 1
Student4: 2
Student5: 3  // Student5 is excluded
Student2: 1
Student4: 2
Student2: 3  // Student2 is excluded

Therefore the next president is Student4, the last one remaining.

Input Specification

The first line will contain a single number \(K\) (\(K < 100\)), which is the number of test cases.

The following \(K\) lines will each contain 2 numbers \(N,M\) (\(N < 10000\), \(M < 100\)).

Output Specification

The output should contain \(K\) lines, each with a single integer which is the remaining students' number.

Sample Input

4
6 2
12 4
8 3
5 3

Sample Output

5
1
7
4