Self-quarantining at home? Well, you’re not the only one since coronaviruses have also been quarantined by your efforts towards wiping them off. There is a coronavirus (Corona-G) who comes up with new mathematical games wherever he is bored. This time also he came up with a game – a game of numbers.
 

He took the first N natural numbers and placed them in a circle such that the numbers 1 and 2 are adjacent, and 1 and N are also adjacent. There is a marker that initially points at 1.

Rotating a circle to the left means that if the marker currently points at number i, then after the rotation it will point at i + 1 if i != N and 1 if i = N.

Rotating a circle to the right means that if the marker currently points at number i, then after the rotation it will point at i – 1  if i != 1 and N if i = 1.
 

Now, he plays K rounds (K is always ODD).

In the 1^st round, he rotates the circle 1² times to the left.

In the 2^nd round, he rotates the circle 2² times to the right.

In the 3^rd round, he rotates the circle 3² times to the left.

In the 4^th round, he rotates the circle 4² times to the right.

In the 5^th round, he rotates the circle 5² times to the left.

And so on till all the rounds are completed.
 

After all the rounds, he found that the marker points at the number X.

Can you find the value of X before Corona-G finishes the game?
 

Input:

• The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
• The first and the only line contains two space-separated integers – N, K.

Output:

For each test case, print a single line containing one integer – X.
 

Constraints:

• 1 < T < 10⁵
• 1 < N < 10⁹
• 1 < K < 10¹⁸
• K is ODD
   

Test Files:

Test File #1 (10 points):

• 1 < T < 5
• 1 < N < 10⁵
• 1 < K < 100

Test File #2 (20 points):

• Sum of K over all test cases does not exceed 10⁶

Test File #3 (70 points): original constraints