#include <bits/stdc++.h> //Andrei Alexandru a.k.a Sho10
#define ll long long
#define double long double
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define aint(a) (a).begin(), (a).end()
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define pi pair
#define rc(s) return cout<<s,0
#define endl '\n'
#define mod 1000000007
#define PI 3.14159265359
#define MAXN 100005
#define INF 1000000005
#define LINF 1000000000000000005ll
#define CODE_START ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
ll t,n,k,a[100005];
int32_t main(){
CODE_START;
cin>>t;
while(t--){
cin>>n>>k;
ll sum=0;
for(ll i=1;i<=n;i++)
{
cin>>a[i];
sum+=a[i];
}
if(n==1){
while(k!=1&&a[1]%2==0){
k/=2;
a[1]/=2;
}
if(k==1){
if(a[1]%2==1){
cout<<"1";
}else cout<<"0";
}else cout<<"1";
continue;
}
sort(a+1,a+n+1);
if(sum%2==1){
cout<<"1";
continue;
}
if(sum%2==0&&k==1){
cout<<"0";
continue;
}
ll ans=0;
for(ll i=1;i<=n;i++)
{
ans+=a[i]/2;
a[i]=a[i]%2;
}
ll cnt=0;
for(ll i=1;i<=n;i++)
{
if(a[i]==1){
cnt++;
}
}
if(ans%2==1&&cnt%2==0){
cout<<"1";
continue;
}
if(ans%2==0&&cnt%2==1){
cout<<"1";
continue;
}
cout<<"0";
}
}
