Description

n个小孩围成一圈做游戏，游戏将决出一个胜利者。

假定一个数m，从第1个小孩起，顺时针数数，每数到第m个小孩时，该小孩离开。接着又从下一个小孩开始数数，数到第m个小孩时，该小孩也离开，如此不断反复进行，最后剩下的一个小孩便是胜利者。对于一定的n、m，究竟胜利者是谁呢？

Input

第一个整数N，表示后面有N组数据，每组数据包含两个整数n和m，分别表示小孩数和游戏中每次数数的个数。

Output

对于每组数据，输出一个整数，表示最后剩下的小孩位置，数与数之间以回车间隔。

Sample

Input

2
10 3
8 3

Output

4
7