ll@t;
rep(t){
	ull@n,@m,@a[n];
	if(n>=m){
		rep(j,18){
			ll k=1<<j;
			if(k&n-m){
				n-=k;
				rep(i,n){
					a[i]+=a[i+k];
				}
			}
		}
	}
	rep(i,n-1){
		rep(j,n-1-i){
			a[j]=(a[j]+a[j+1])**2;
		}
	}
	wt(a[0]%2**m);
}