#include <iostream> #include <map> using namespace std; void solve() { int n,k; cin>>n>>k; int m=(1<<(1+__lg(k))); int a[n]; bool fl=0; for(int i=0;i<n;i++)cin>>a[i]; // for(int kp:{1,2,3,4,5,6,k}) // { // if(kp<=k) // { int sm=0; for(int i=0;i<n;i++)sm=(sm^(a[i]%m)); if(sm and !fl) { fl=1; cout<<1; } // } // } if(!fl){ cout<<0; } } map<pair<int,int>,bool> res; bool f(int x,int lim) { if(res.find({x,lim})!=res.end())return res[{x,lim}]; bool wn=0; for(int y=1;y<=lim and y<=x;y++) { wn|=(!f(x-y,y)); } return res[{x,lim}]=wn; } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); // int k,n; // cin>>k; // for(n=1;n<=100*k;n++) // { // if(!f(n,k)) // { // cout<<"Fails at "<<n<<' '<<n%(1<<(1+__lg(k)))<<' '<<(1<<(1+__lg(k)))<<endl;; // } // } // while(1) // { // cin>>n; // cout<<"Results "<<f(n,k)<<endl; // } int t; cin>>t; while(t--)solve(); cout<<endl; }