Migrated from Lutece 965 约瑟夫斯问题

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

据传说，罗马人攻夺Jotapat后，Josephus和朋友两人与其他n个犹太人避难到一个洞穴里。使Josephus非常反感的是，他发现除了他自己和朋友外，其余的都决心殉难以免落入征服者的手中。他不敢太公然表示反对而只好同意了，但他坚持这一行动必须有条不紊地进行，并且建议大家坐成一圆圈，然后从洞口的人开始顺时针报数，数到$m$的人就杀掉，然后又从下一个人开始从$1$报数，直到最后一个人去自杀。问Josephus应该把自己和朋友放在第几个位置，才能避免被杀掉。注意：本题要求用链表实现。

Input

本题有多组测试数据，第一行是测试数据组数$T$，下面$T$行的每一行有两个用一个空格隔开的数$n$、$m$，表示犹太人数和报的数。其中$1\le n\le 99$，$1\le m\le 999$。

Output

输出共有$T$行，依次对应输入行。每行有两个数，从小到大排列，并用空格隔开。注意第二个数后没有空格。

Samples

5
39 3
25 5
2 2
1 9
99 501

16 31
18 27
1 3
1 2
17 94

Note

位置是从洞口顺时针从$1$依次编号，报数也是从位置$1$的人顺时针报数。

Resources

wxiaoping 2009年C语言第八次上机