#include <bits/stdc++.h>
#define BIT 61
#define SIZ 13
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,p[4300009],ct,co[755][755][16],iv[4300009];
bitset f[755],qq[755][755],va[4300009];
int dp[755][755];
bool cmp(int x,int y) {
	return va[x]<va[y];
}
bool chk(int cl) {
	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)||(co[i][r][j-r]>cl)) {
				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=1;
	while(T--) {
		std::mt19937 rng(114);
		scanf("%d %d",&N,&K);
//		N=750;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];
			}
		}
		ct=0;
		for(int i=1;i<=N;i++) {
			for(int j=i;j<=N;j++) {
				for(int k=j;k<=j+14&&k<=N;k++) {
					co[i][j][k-j]=++ct;
					p[ct]=ct;
					va[ct]=(qq[i][j]>>k-j);
				}
			}
			//printf("%d\n",ct);
		}
		std::sort(p+1,p+ct+1,cmp);
		for(int i=1;i<=ct;i++) {
			iv[p[i]]=i;
		}
		for(int i=1;i<=N;i++) {
			for(int j=i;j<=N;j++) {
				for(int k=j;k<=j+14&&k<=N;k++) {
					co[i][j][k-j]=iv[co[i][j][k-j]];
				}
			}
		}
		int l=1,r=ct,mm;
		while(l<r) {
			mm=(l+r)/2;
			if(chk(mm)) r=mm;else l=mm+1;
		}
		bitset ff=va[p[l]];
		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");
	}
}