#include<iostream>
using namespace std;
int main(){
unsigned long long int fib[100];
fib[1]=1;
fib[2]=1;
for(int i=3;i<100;++i){
if(fib[i-1]+fib[i-2]<2000000000)
fib[i]=fib[i-1]+fib[i-2];
else
fib[i]=2000000000;
}
bool arr[8]={1,0,1,1,0,1,0,1};
int m;
while(cin >> m){
for(int i=0;i<m;++i){
unsigned long long int n,k;
cin >> n >> k;
if(k>fib[n]){
printf("-1\n");
continue;
}
if(k<=2)
if(n%2==0 && k==1)
printf("1\n");
else if(n%2==0 && k==2)
printf("0\n");
else if(n%2==1 && k==1)
printf("0\n");
else
printf("1\n");
else
cout << arr[(k-2)%8-1] << endl;
}
}
return 0;
}
雖然之前也有人發過類似的問題，
不過看了以後還是沒能解決，
希望有大大能幫忙一下了...