Description

由于众所周知的原因, 冈部一直欠真由理一串香蕉. 为了封上真由理的嘴, 冈部承诺只要真由理回答出这个问题, 就给她买一车的香蕉: 一开始有n 个人围成一个圈, 从1 开始顺时针报数, 报出m 的人被机关处决. 然后下一个人再从1 开始报数, 直到只剩下一个人. 红莉栖: “这不就是约瑟夫问题吗…” 伦太郎: “助手你给我闭嘴!” 真由理虽然已经晕头转向了, 但听到有一车的香蕉, 两眼便放出了光芒. “那个呢, 真由氏很想要一车子的香蕉呢. 如果可以帮帮我的话, 我可以把一些香蕉分给你哟, 诶嘿嘿. 拜托你啦.”

Input

第一行一个整数T, 表示数据组数. 接下来T 行, 每行两个整数n;m.

Output

对于每组数据, 输出一行一个整数, 表示幸存者的编号.

Sample Input

5 4 6 2 8 2 9 8 8 7 9

Sample Output

3 1 2 4 7

Data Constraint

Solution

经典的 Josephus 问题, 参见 Wikipedia 。网址：Josephus Problem

设函数 f(n,m) 表示 n,m 的答案，那么就有：

时间复杂度 O(m log n) 。

Code

#include<cstdio> using namespace std; inline int read() { int X=0,w=1; char ch=0; while(ch<'0' || ch>'9') {if(ch=='-') w=-1;ch=getchar();} while(ch>='0' && ch<='9') X=(X<<3)+(X<<1)+ch-'0',ch=getchar(); return X*w; } inline int f(int x,int y) { if(x==1) return 0; if(x<y) return (f(x-1,y)+y)%x; int x1=x-x/y; return (long long)(f(x1,y)-x%y+x1)%x1*y/(y-1); } int main() { int T=read(); while(T--) { int n=read(),m=read(); printf("%d\n",f(n,m)+1); } return 0; }