f[1<<21];g[1<<21];d;v(x){return--d&31?x*v(x*x):1;}a;main(b,c){for(*f=1;b=ffs(++a)%22;f[a]=f[a-1]*(a>>--b),g[a]=g[a-1]+b);for(gets(&a);d=~scanf("%d%d%d",&a,&b,&c);puts(--c&1|(f[c+b]*v(f[b])*v(f[c])*-~c<<g[c+b]-g[b]-g[c])-1&a?"0":"1"));}