P4101
#include<bits/stdc++.h>
#define int long long
signed main(){
ios::sync_with_stdio(0);
int t, n, m;
cin >> t;
while(t--)
{
cin >> n >> m;
if(n <= m)
{
cout << (n & 1)<< "\n";
continue;
}
if(m & 1) //m是奇数
{
if(n % m % 4 < 2) puts("1");
else puts("0");
}
else //m是偶数
{
if(n % m % 4 < 2) puts("0");
else puts("1");
}
}
return 0;
}