All Submissions


Background

HOBO had thrown a party and as a gracious host he decided to organize a game. N people are made to stand in a circle and the kth person is eliminated (counting starts from the first person) and the circle shrinks subsequently. The game is played until a single person remains.Hobo wants his friend Rolly (who is quite genius)to win the game.The position number in the circle starts from 1 and the kth person is first to be eliminated, after elimination the counting again starts from the person who was adjacent to the eliminated person.

You need to find the position in the circle where rolly should stand to ensure his victory.

Input

1st line: An Integer T denoting the number of test cases. Each test Case Contains: two integers N and K.

Output

Print the position in the circle where rolly should stand.

Sample Input


2
7 3
7 4


Sample Output


4
2


Constraints

Number of Test Cases T , 1 < T <= 100

1 < N <= 10^6

1 < K <= 1000

Problem Setter : Vivek Bhatnagar

Note: We know that this problem is similar to one given not too long ago. This is intentional.

Languages: C,C++,Java

Time Limit: 2 Second(s)
Score: 100 Point(s)
Input File Limit: 50000 Bytes

Submit

Login to post clarification.

No Clarifications.

Contest

Mode Judge

Passive

Online

Overall Rankings

RankNameScore
1xyz0
2Ams0
3TIP0
4team420
5xyzz0
6asdasdasd0
7abcd0
8khankhan0
9Gabriel0
10gigel0