#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;
}
