//HDOJ 4203 Doubloon Game 博弈 找规律
/*
题意：有n个硬币，两个人轮流取，每次只能取m个pow,(1,m,m^2...)
如果先手必败输出0，否则输出第一步最少取走的硬币数量
思路：找规律
当n=2时：
0 1 2 |3 4 5 |6 7 8 9 ...
P N N |P N N |P N N P ...
当n=3时:
0 1 2 3 4 5 6 7 8 9 ...
P N P N P N P N P N ...
当n=4时:
0 1 2 3 4 |5 6 7 8 9 |...
P N P N N |P N P N N |...
当n=5时:
0 1 2 3 4 5 6 7 8 9 ...
P N P N P N P N P N ...
...
*/
#include
#include
#include
int T,n,m;
int main(){
scanf("%d",&T);
while(T--){
scanf("%d %d",&n,&m);
if(m%2){
puts(n%2 "1":"0");
} www.2cto.com
else{
n %= (m+1);
if(n==m)
printf("%d\n",m);
else
puts(n%2 "1":"0");
}
}
return 0;
}