#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define N 1000000007
int compare(const void * a, const void * b) 
{ 
    return ( *(int*)b - *(int*)a ); 
}
int main()
{
    int T,n,b,x,a,i,j,c,k; 
    int A[100000]={0};
    long long int l,m;
    scanf("%d",&T);
    for(k=1;k<=T;k++)
    {   i=0;
        scanf("%d %d",&a,&x);
        b=pow(2,x);
        c=b;
        while(b<a){
            b=b+c-1;
        }
        printf("%d\n",b==a);
    }
    return 0;
}
 

I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdGRsaWIuaD4KI2luY2x1ZGUgPHN0cmluZy5oPgojaW5jbHVkZSA8bWF0aC5oPgojZGVmaW5lIE4gMTAwMDAwMDAwNwppbnQgY29tcGFyZShjb25zdCB2b2lkICogYSwgY29uc3Qgdm9pZCAqIGIpIAp7IAogICAgcmV0dXJuICggKihpbnQqKWIgLSAqKGludCopYSApOyAKfQppbnQgbWFpbigpCnsKICAgIGludCBULG4sYix4LGEsaSxqLGMsazsgCiAgICBpbnQgQVsxMDAwMDBdPXswfTsKICAgIGxvbmcgbG9uZyBpbnQgbCxtOwogICAgc2NhbmYoIiVkIiwmVCk7CiAgICBmb3Ioaz0xO2s8PVQ7aysrKQogICAgeyAgIGk9MDsKICAgICAgICBzY2FuZigiJWQgJWQiLCZhLCZ4KTsKICAgICAgICBiPXBvdygyLHgpOwogICAgICAgIGM9YjsKICAgICAgICB3aGlsZShiPGEpewogICAgICAgICAgICBiPWIrYy0xOwogICAgICAgIH0KICAgICAgICBwcmludGYoIiVkXG4iLGI9PWEpOwogICAgfQogICAgcmV0dXJuIDA7Cn0K

MQo0IDI=

1
4 2