#include<stdio.h>

const long mod=1048576;
long kai[2000000];
int pow[2000000];
int main(){
	long t,e,i=0;
	long a,b,c,d;
	kai[0]=1;
	scanf("%ld",&t);
	for(;t>0;t--){
		scanf("%ld %ld %ld",&a,&b,&c);
		if(c%2==0){
			printf("0\n");
		}else{
			for(;i<b+c-1;i++){
				if(i%2==0){
					kai[i+1]=kai[i]*(i+1)%mod;
					pow[i+1]=pow[i];
				}else{
					kai[i+1]=kai[i];
					pow[i+1]=pow[i]+1;
				}
			}
			d=(kai[b+c-1]/kai[b]/kai[c-1])*c%mod;
			e=pow[b+c-1]-pow[b]-pow[c-1];
			d=d << e;
			d=(d+a-1)%mod;
			if((d&a)==a){
				printf("1\n");
			}else{
				printf("0\n");
			}
		}
	}
	return 0;
}