#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define OYY LLONG_MAX
#define mod 998244353
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define FOR for(int i=1;i<=n;i++)
#define mid (start+end)/2
#define lim 1000005
#define fi first
#define se second
int dp[102][102];
inline int findd(int x,int k){
//cout<<x<<" "<<k<<" "<<tut<<endl;
if(x==0){
return 0;
}
if(~dp[x][k])return dp[x][k];
int cev=0;
for(int i=k;i>=1;i--){
if(x-i>=0){
if((findd(x-i,i)+1)&1)cev=1;
}
}
return dp[x][k]=cev;
}
int32_t main(){
faster
int t;cin>>t;
while(t--){
int n,k;cin>>n>>k;
int dizi[n+1];
int sum=0,tut=0;
FOR{
cin>>dizi[i];
sum+=dizi[i];
tut+=dizi[i]/2;
}
if(n==1){
memset(dp,-1,sizeof(dp));
cout<<findd(dizi[1],k);
/*if(dizi[1]<=k || dizi[1]&1)cout<<"1";
else{
if(tut&1)cout<<"1";
else cout<<"0";
}*/
}
else if(k==1){
if(sum&1)cout<<"1";
else cout<<"0";
}
else{
if(tut&1 || sum&1)cout<<"1";
else cout<<"0";
}
}
cout<<'\n';
return 0;
}
