Game Of Life

All submissions for this problem are available.
Joseph is captured along with N1 of his soldier friends. The enemy has decided to play the following game.
These N soldiers are seated in a circle. The seats are numbered from 1 to N in clockwise order. The enemy chooses a nonzero integer K.
If K is positive the enemy kills the K^{th} guy in clockwise direction starting from 1 (the 1st guy starting from 1 is 1 itself). Then the (2K)^{th} alive guy in anticlockwise direction from the position of first killing, then (3K)^{th} alive guy in clockwise direction from position of second killing and so on until only one guy survives.
Similarly, if K is negative the enemy kills the K^{th} guy in anticlockwise direction starting from 1. Then the (2K)^{th} guy in clockwise direction from the position of first killing, then (3K)^{th} guy in anticlockwise direction from the position of second killing and so on until only one guy survives.
That is, after every killing the enemy reverses its direction and increases the number of soldiers skipped before next killing by K.
Note that the starting direction is clockwise if K>0 and anticlockwise if K<0 and the counting for the next killing starts from the position of previous killing.
You have to determine the index at which Joseph should sit in order to survive.
Input
The first line of the input contains an integer T denoting the number of test cases.
Each of the following T lines contain two integers each: N and K.
Output
For each test case, output a single integer in a new line: the index where Joseph must choose to survive.
Constraints
 1 ≤ T ≤ 10^{4}
 1 ≤ N ≤ 10^{6}
 10^{9} ≤ K ≤ 10^{9}
 K is nonzero.
Sum of N over all testcases is less than or equal to 10^{6} for each input file
Example
Input: 2 4 2 4 1 Output: 3 4
Explanation
Test Case 1.
Step 1: Enemy kills the 2nd person clockwise starting from 1. That is, 2 is killed. [Going clockwise]
Step 2: Enemy skips (1,4,3) and kills (1) [Going anticlockwise]
Step 3: Enemy skips (3,4,3,4,3) and kills (4) [Going clockwise]
3 survives
Test case 2:Step 1: Enemy kills first person starting from 1. That is, enemy skips (none) and kills (1) [Going anticlockwise]
Step 2: Enemy skips (2) and kills (3) [Going clockwise]
Step 3: Enemy skips (2,4) and kills (2) [Going anticlockwise]
4 survives
Author:  varunkhare1234 
Tags  varunkhare1234 
Date Added:  18042017 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.9.2, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.4, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions