#include <bits/stdc++.h>
#define BIT 61
#define SIZ 15
struct bitset {
	long long bits[SIZ];
	void init(void) {for(int i=0;i<SIZ;i++) bits[i]=0;} 
	void set(int x,bool y) {bits[x/BIT]^=((((bits[x/BIT]>>(x%BIT))&1)^y)<<(x%BIT));}
	void setall(bool y) {for(int i=0;i<SIZ;i++) bits[i]=((((long long)y)<<BIT)-(long long)(y));}
	bool q(int x) {return (bits[x/BIT]>>(x%BIT))&1;}
	void operator=(const bitset& y) {for(int i=0;i<SIZ;i++) bits[i]=y.bits[i];}
	void operator|=(const bitset& y) {for(int i=0;i<SIZ;i++) bits[i]|=y.bits[i];}
	void operator&=(const bitset& y) {for(int i=0;i<SIZ;i++) bits[i]&=y.bits[i];}
	void operator^=(const bitset& y) {for(int i=0;i<SIZ;i++) bits[i]^=y.bits[i];}
	void operator+=(const bitset& y) {
		for(int i=0;i<SIZ;i++) {
			bits[i]+=y.bits[i];
			if((bits[i]>>BIT)&1) bits[i]^=(1ll<<BIT),bits[i+1]++;
		}
	}
	void operator-=(const bitset& y) {
		for(int i=0;i<SIZ;i++) {
			bits[i]-=y.bits[i];
			if(bits[i]<0) bits[i]+=(1ll<<BIT),bits[i+1]--;
		}
	}	
	void operator<<=(int k) {
		bitset z;z.init();
		int tmp=k/BIT;
		for(int i=0;i<SIZ-tmp;i++) z.bits[i+tmp]=bits[i];
		k%=BIT;
		z.bits[SIZ-1]<<=k;
		for(int i=SIZ-2;i>=0;i--) {
			long long tmp=z.bits[i];
			z.bits[i]&=((1ll<<(BIT-k))-1);
			z.bits[i+1]|=((tmp^z.bits[i])>>(BIT-k));
			z.bits[i]<<=k;
		}
		for(int i=0;i<SIZ;i++) bits[i]=z.bits[i];
	}
	void operator>>=(int k) {
		bitset z;z.init();
		int tmp=k/BIT;
		for(int i=tmp;i<SIZ;i++) z.bits[i-tmp]=bits[i];
		k%=BIT;
		z.bits[0]>>=k;
		for(int i=1;i<SIZ;i++) {
			z.bits[i-1]|=((z.bits[i]&((1ll<<k)-1))<<(BIT-k));
			z.bits[i]>>=k;
		}
		for(int i=0;i<SIZ;i++) bits[i]=z.bits[i];
	}	
	bitset operator|(const bitset& y) {
		bitset z;
		for(int i=0;i<SIZ;i++) z.bits[i]=bits[i]|y.bits[i];
		return z;
	}
	bitset operator&(const bitset& y) {
		bitset z;
		for(int i=0;i<SIZ;i++) z.bits[i]=bits[i]&y.bits[i];
		return z;
	}
	bitset operator^(const bitset& y) {
		bitset z;
		for(int i=0;i<SIZ;i++) z.bits[i]=bits[i]^y.bits[i];
		return z;
	}	
	bitset operator+(const bitset& y) {
		bitset z;z.bits[0]=0;
		for(int i=0;i<SIZ;i++) {
			z.bits[i]+=bits[i]+y.bits[i];
			if((z.bits[i]>>BIT)&1) z.bits[i]^=(1ll<<BIT),z.bits[i+1]=1;else z.bits[i+1]=0;
		}
		return z;
	}
	bitset operator-(const bitset& y) {
		bitset z;z.bits[0]=0;
		for(int i=0;i<SIZ;i++) {
			z.bits[i]+=bits[i]-y.bits[i];
			if(z.bits[i]<0) z.bits[i]+=(1ll<<BIT),z.bits[i+1]=-1;else z.bits[i+1]=0;
		}
		return z;
	}
	bitset operator<<(int k) {
		bitset z;z.init();
		int tmp=k/BIT;
		for(int i=0;i<SIZ-tmp;i++) z.bits[i+tmp]=bits[i];
		k%=BIT;
		z.bits[SIZ-1]<<=k;
		for(int i=SIZ-2;i>=0;i--) {
			long long tmp=z.bits[i];
			z.bits[i]&=((1ll<<(BIT-k))-1);
			z.bits[i+1]|=((tmp^z.bits[i])>>(BIT-k));
			z.bits[i]<<=k;
		}
		return z;
	}
	bitset operator>>(int k) {
		bitset z;z.init();
		int tmp=k/BIT;
		for(int i=tmp;i<SIZ;i++) z.bits[i-tmp]=bits[i];
		k%=BIT;
		z.bits[0]>>=k;
		for(int i=1;i<SIZ;i++) {
			z.bits[i-1]|=((z.bits[i]&((1ll<<k)-1))<<(BIT-k));
			z.bits[i]>>=k;
		}
		return z;
	}	
	int count(void) {
		int ans=0;
		for(int i=0;i<SIZ;i++) ans+=__builtin_popcountll(bits[i]);
		return ans;
	}
	bool operator<(const bitset& y) {
		for(int i=SIZ-1;i>=0;i--) if(bits[i]^y.bits[i]) return bits[i]<y.bits[i];
		return 0;
	}
	bool operator>(const bitset& y) {
		for(int i=SIZ-1;i>=0;i--) if(bits[i]^y.bits[i]) return bits[i]>y.bits[i];
		return 0;
	}
	bool operator<=(const bitset& y) {
		for(int i=SIZ-1;i>=0;i--) if(bits[i]^y.bits[i]) return bits[i]<y.bits[i];
		return 1;
	}
	bool operator>=(const bitset& y) {
		for(int i=SIZ-1;i>=0;i--) if(bits[i]^y.bits[i]) return bits[i]>y.bits[i];
		return 1;
	}
	bool operator==(const bitset& y) {
		for(int i=SIZ-1;i>=0;i--) if(bits[i]^y.bits[i]) return 0;
		return 1;
	}
}; 
bitset max(bitset& x,bitset& y) {
	for(int i=SIZ-1;i>=0;i--) {
		if(x.bits[i]>y.bits[i]) return x;
		if(x.bits[i]<y.bits[i]) return y;
	}
	return x;
}
bitset min(bitset& x,bitset& y) {
	for(int i=SIZ-1;i>=0;i--) {
		if(x.bits[i]>y.bits[i]) return y;
		if(x.bits[i]<y.bits[i]) return x;
	}
	return x;
}
int T,N,a[20009],K;
bitset f[755],qq[755][755];
int dp[755][755];
bool chk(bitset x) {
	dp[N+1][N+1]=0;
	for(int i=N;i>=1;i--) {
		dp[i][N+1]=0x3f3f3f3f;
		int r=N;
		for(int j=N;j>=i;j--) {
			dp[i][j]=dp[i][j+1];
			while((r>j)||(qq[i][r]>(x<<(j-r)))) {
				r--;
			}
			dp[i][j]=std::min(dp[i][j],dp[r+1][j+1]+(j-i));
			//for(int k=j;k>=i;k--) {
			//	if((qq[i][k]<=(x<<(j-k)))) {
//					printf("%d %d %d %d %d\n",i,k,j,qq[1][1].count(),x.count());
			//		break;
			//	} 
			//}
		}
	}
	if(dp[1][1]<=K) return 1;
	return 0;
}
signed main(void) {
	scanf("%d",&T);
//	T=50;
	while(T--) {
		std::mt19937 rng(114);
		scanf("%d %d",&N,&K);
//		N=15;K=10000;
		for(int i=1;i<=N;i++) {
			scanf("%d",&a[i]);
		//	a[i]=rng()%1000000+1;
			f[i].setall(0);
			f[i].bits[0]=a[i];
			f[i]<<=N;
		}
		for(int i=1;i<=N;i++) {
			qq[i][i]=f[i];
			for(int j=i+1;j<=N;j++) {
				qq[i][j]=(qq[i][j-1]>>1);
				qq[i][j]+=f[j];
			}
		}
		bitset ff;
		for(int i=N+20;i>=0;i--) ff.set(i,1);
		for(int i=N+20;i>=std::max(N-30,0);i--) {
			ff.set(i,0);
			if(!chk(ff)) {
				ff.set(i,1);
			}
		}
		int st=0;
		for(int i=N+20;i>=0;i--) {
			if(ff.q(i)) {
				st=i;
				break;
			}
		}
		for(int i=st;i>=0;i--) printf("%d",ff.q(i));
		printf("\n");
	}
}