#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
using ull = unsigned long long;
const int N = 2e4 + 35, lim = 22, mod1 = 998244353, mod2 = 1e9 + 7, inf = 1e9 + 2;
mt19937 rnd(0);
int tt, n, K, a[N], cur[N], prehigh[N], suf1[N];
int log2n, st[N][25];
int pre2[N], sum2[N];
ull sum[N][lim + 5];
int pw1[N * 2], pw2[N * 2], inv1[N * 2], inv2[N * 2];
int rt[N];
struct Msg{
	int len, a1, a2;
	Msg(){}
	Msg(int len, int a1, int a2) : len(len), a1(a1), a2(a2) {}
	friend Msg operator + (const Msg &a, const Msg &b){
		return Msg(a.len + b.len, (a.a1 + 1ll * b.a1 * pw1[a.len]) % mod1, (a.a2 + 1ll * b.a2 * pw2[a.len]) % mod2);
	}
}all1[N];
bool same(const Msg &a, const Msg &b){
	return a.len == b.len && a.a1 == b.a1 && a.a2 == b.a2;
}
struct Str{
	int k, highbit, lowbit, b[N];
	int hs1[N], hs2[N];
	void init(int l, int r, int _k){
		for (int i = 1; i <= n + lim; i++) b[i] = 0;
		for (int i = l; i <= r; i++)
			for (int j = 0; j < lim; j++)
				if ((a[i] >> j) & 1)
					b[i + j]++;
		int c = 0;
		for (int i = 1; i <= n + lim; i++){
			c += b[i];
			b[i] = c % 2;
			c /= 2;
			if (b[i]) highbit = i;
		}
		for (int i = n + lim; i >= 1; i--)
			if (b[i])
				lowbit = i;
		for (int i = 1; i <= n + lim; i++){
			hs1[i] = (hs1[i - 1] + 1ll * b[i] * pw1[i]) % mod1;
			hs2[i] = (hs2[i - 1] + 1ll * b[i] * pw2[i]) % mod2;
		}
	}
	Msg ask(int l, int r) const{
		int l2 = max(1, l), r2 = min(n + lim, r);
		int x1 = (hs1[r2] - hs1[l2 - 1] + mod1) % mod1, x2 = (hs2[r2] - hs2[l2 - 1] + mod2) % mod2;
		if (l >= 0) return Msg(r - l + 1, 1ll * x1 * inv1[l] % mod1, 1ll * x2 * inv2[l] % mod2);
		else return Msg(r - l + 1, 1ll * x1 * pw1[-l] % mod1, 1ll * x2 * pw2[-l] % mod2);
	}
	int ask(int x) const{
		if (1 <= x && x <= n + lim) return b[x];
		else return 0;
	}
};
struct tree{
#define mid ((l + r) >> 1)
	int tot;
	struct node{
		int ls, rs;
		Msg msg;
	}a[N * 22 * 22];
	void build(int &p, int l, int r){
		p = ++tot;
		if (l == r){
			a[p].msg = Msg(1, 0, 0);
			return;
		}
		build(a[p].ls, l, mid);
		build(a[p].rs, mid + 1, r);
		a[p].msg = a[a[p].ls].msg + a[a[p].rs].msg;
	}
	void add(int &p, int o, int l, int r, int s, int k){
		a[p = ++tot] = a[o];
		if (l == r){
			a[p].msg = Msg(1, k, k);
			return;
		}
		if (s <= mid) add(a[p].ls, a[o].ls, l, mid, s, k);
		else add(a[p].rs, a[o].rs, mid + 1, r, s, k);
		a[p].msg = a[a[p].ls].msg + a[a[p].rs].msg;
	}
	Msg ask(int p, int l, int r, int s, int t){
		if (s <= l && r <= t) return a[p].msg;
		Msg res(0, 0, 0);
		if (s <= mid) res = res + ask(a[p].ls, l, mid, s, t);
		if (t > mid) res = res + ask(a[p].rs, mid + 1, r, s, t);
		return res;
	}
	Msg ask(int p, int l, int r, int s){
		return ask(p, l, r, s, s);
	}
	int askr(int p, int l, int r, int s){
		if (a[p].msg.a1 == 0 && a[p].msg.a2 == 0) return 0;
		if (s <= l){
			if (l == r) return l;
			int res = askr(a[p].ls, l, mid, s);
			if (res) return res;
			else return askr(a[p].rs, mid + 1, r, s);
		}
		if (s <= mid){
			int res = askr(a[p].ls, l, mid, s);
			if (res) return res;
			else return askr(a[p].rs, mid + 1, r, s);
		}else return askr(a[p].rs, mid + 1, r, s);
	}
	int ask2(int p, int l, int r, int s, int t, const Str &str){
		if (r <= s){
			if (same(a[p].msg, str.ask(t - (s - l), t - (s - r)))) return l - 1;
			if (l == r) return l;
			int res = ask2(a[p].rs, mid + 1, r, s, t, str);
			if (res > mid) return res;
			else return ask2(a[p].ls, l, mid, s, t, str);
		}
		if (mid < s){
			int res = ask2(a[p].rs, mid + 1, r, s, t, str);
			if (res > mid) return res;
			else return ask2(a[p].ls, l, mid, s, t, str);
		}else return ask2(a[p].ls, l, mid, s, t, str);
	}
#undef mid
}T;
template<typename T> int cmp(T a, T b){
	if (a > b) return 1;
	else if (a == b) return 0;
	else return -1;
}
struct Msg2{
	int tp, len, num;
	Msg2(){}
	Msg2(int tp, int len, int num) : tp(tp), len(len), num(num) {}
};
struct Msg3{
	int l, r, k;
	Msg3(){}
	Msg3(int l, int r, int k) : l(l), r(r), k(k) {}
};
int C;
struct Compare{
	int k1;
	Str str;
	int pos[N], state[N], lstpos[N];
	void init(int l, int r, int k){
		k1 = k;
		str.init(l, r, k1);
		for (int i = 1; i <= n + lim; i++) lstpos[i] = str.b[i] ? i : lstpos[i - 1];
		for (int i = 1; i <= n; i++){
			pos[i] = T.ask2(rt[i], 1, n + lim, prehigh[i], str.highbit, str);
			if (pos[i] == 0){
				int d = str.highbit - prehigh[i];
				if (d > 0 && lstpos[d]){
					pos[i] = lstpos[d] - d;
					state[i] = 1;
				}else pos[i] = -inf;
			}else state[i] = cmp(str.ask(str.highbit - (prehigh[i] - pos[i])), T.ask(rt[i], 1, n + lim, pos[i]).a1);
		}
	}
	int ask(int l, int r, int k2){C++;
		vector<Msg2> vec; int ph;
		if (r - l <= lim){
			ull x = sum[l][r - l], bits = 63 ^ __builtin_clzll(x);
			ph = l + bits;
			if (bits >= lim) vec = {Msg2(0, lim, x & ((1 << lim) - 1)), Msg2(0, bits - lim + 1, x >> lim)};
			else vec = {Msg2(0, bits + 1, x)};
		}else{
			int a = sum2[l], b = pre2[l - 1] / 2;
			if (a >= b) vec = {Msg2(0, lim, a - b), Msg2(2, prehigh[r] - (l + lim - 1), 0)}, ph = prehigh[r];
			else{
				int p = suf1[l + lim] < r ? suf1[l + lim] : r + __builtin_ctz(pre2[r]);
				if (p < prehigh[r]) vec = {Msg2(0, lim, (1 << lim) + a - b), Msg2(1, p - (l + lim), 1), Msg2(1, 1, 0), Msg2(2, prehigh[r] - p, 0)}, ph = prehigh[r];
				else vec = {Msg2(0, lim, (1 << lim) + a - b), Msg2(1, p - (l + lim), 1)}, ph = prehigh[r] - 1;
			}
		}
		if (str.highbit + k1 != ph + k2) return cmp(str.highbit + k1, ph + k2);
		int curlen = 0;
		while (!vec.empty()){
			Msg2 msg = vec.back();
			vec.pop_back();
			Msg res = str.ask(str.highbit - curlen - msg.len + 1, str.highbit - curlen);
			if (msg.tp == 0){
				int a = res.a1, b = msg.num;
				if (a != b) return cmp(a, b);
			}else if (msg.tp == 1){
				if (msg.num == 0 && !same(res, Msg(msg.len, 0, 0))) return 1;
				else if (msg.num == 1 && !same(res, all1[msg.len])) return -1;
			}else if (msg.tp == 2){
				if (ph - pos[r] < msg.len) return state[r];
			}
			curlen += msg.len;
		}
		if (curlen <= str.highbit - str.lowbit) return 1;
		else return 0;
	}
}C1, C2;
int f[N][lim + 5];
struct tree2{
#define mid ((l + r) >> 1)
#define ls (now << 1)
#define rs (now << 1 | 1)
	int a[N << 2];
	void build(int now, int l, int r){
		a[now] = inf;
		if (l == r) return;
		build(ls, l, mid);
		build(rs, mid + 1, r);
	}
	void add(int now, int l, int r, int s, int k){
		if (l == r){
			a[now] = k;
			return;
		}
		if (s <= mid) add(ls, l, mid, s, k);
		else add(rs, mid + 1, r, s, k);
		a[now] = min(a[ls], a[rs]);
	}
	int ask(int now, int l, int r, int s, int t){
		if (s <= l && r <= t)
			return a[now];
		int res = inf;
		if (s <= mid) res = min(ask(ls, l, mid, s, t), res);
		if (t > mid) res = min(ask(rs, mid + 1, r, s, t), res);
		return res;
	}
#undef mid
#undef ls
#undef rs
}T2;
bool check(Msg3 curans){
	C1.init(curans.l, curans.r, curans.k);
	T2.build(1, 0, n);
	T2.add(1, 0, n, 0, 0);
	for (int i = 1; i <= n; i++){
		int rr = i - 1;
		bool flg = 0;
		for (int j = 0; j < lim && i + j <= n; j++)
			if (flg || C1.ask(i, i, n - (i + j)) >= 0){
				while (i - rr <= lim && rr > 0 && C1.ask(rr, i, n - (i + j)) >= 0) rr--;
				if (i - rr > lim){
					int l = 0, r = rr, mid;
					while (l <= r){
						mid = (l + r) >> 1;
						if (C1.ask(mid + 1, i, n - (i + j)) >= 0) r = mid - 1;
						else l = mid + 1;
					}
					rr = l;
				}
				f[i][j] = j ? f[i][j - 1] : inf;
				if (rr >= 0 && rr < i - lim) f[i][j] = min(T2.ask(1, 0, n, rr, i - lim - 1) + i + j - 1, f[i][j]);
				for (int k = max(i - lim, rr); k < i; k++) f[i][j] = min(f[k][min(lim - 1, j + (i - k - 1))] + i - k - 1 + j, f[i][j]);
				flg = 1;
			}else f[i][j] = inf;
		T2.add(1, 0, n, i, f[i][lim - 1] - i);
	}
	return f[n][0] <= K;
}
void solve(){
	cin >> n >> K;
	T.tot = 0;
	for (int i = 0; i <= n + lim; i++) cur[i] = 0;
	T.build(rt[0], 1, n + lim);
	for (int i = 1; i <= n; i++){
		rt[i] = rt[i - 1];
		cin >> a[i];
		int c = 0;
		prehigh[i] = prehigh[i - 1];
		for (int j = 0; j < lim; j++){
			c = c + ((a[i] >> j) & 1) + cur[i + j];
			if (cur[i + j] != c % 2) T.add(rt[i], rt[i], 1, n + lim, i + j, c % 2);
			cur[i + j] = c % 2;
			if (c) prehigh[i] = max(i + j, prehigh[i]);
			c /= 2;
		}
		pre2[i] = pre2[i - 1] / 2 + a[i];
	}
	suf1[n + lim + 1] = n + lim + 1;
	for (int i = n + lim; i >= 1; i--) suf1[i] = cur[i] ? i : suf1[i + 1];
	for (int i = 1; i <= n + lim; i++){
		sum2[i] = 0;
		for (int j = 0; j < lim && i + j <= n + lim; j++)
			if (cur[i + j])
				sum2[i] |= 1 << j;
	}
	for (int l = 1; l <= n; l++){
		ull cur = 0;
		for (int r = l; r <= n && r - l <= lim; r++){
			cur += (1ll * a[r]) << (r - l);
			sum[l][r - l] = cur;
		}
	}
	Msg3 Ml(1, 1, 0), Mr(1, n, n - 1), Mmid, ans;
	for (int i = 2; i <= n && i - Ml.l <= lim; i++)
		if (((1ll * a[i]) << (i - Ml.l)) < a[Ml.l])
			Ml = Msg3(i, i, 0);
	while (1){
		C1.init(Ml.l, Ml.r, Ml.k);
		C2.init(Mr.l, Mr.r, Mr.k);
		vector<array<int, 4>> vec;
		for (int i = 1; i <= n; i++){
			int l = i + 1, r = i;
			for (int j = 0; i + j <= n && j < lim; j++){
				if (r > 0 && C1.ask(r, i, n - (i + j)) != -1){
					int l2 = 1, r2 = r - 1, mid;
					while (l2 <= r2){
						mid = (l2 + r2) >> 1;
						if (C1.ask(mid, i, n - (i + j)) == -1) l2 = mid + 1;
						else r2 = mid - 1;
					}
					r = r2;
				}
				if (l > 1 && C2.ask(l - 1, i, n - (i + j)) == 1){
					int l2 = 1, r2 = l - 1, mid;
					while (l2 <= r2){
						mid = (l2 + r2) >> 1;
						if (C2.ask(mid, i, n - (i + j)) == 1) r2 = mid - 1;
						else l2 = mid + 1;
					}
					l = l2;
				}
				if (l <= r) vec.push_back({i, n - (i + j), l, r});
			}
		}
		long long sz = 0;
		for (auto [r, k, l1, l2] : vec) sz += l2 - l1 + 1;
		if (sz == 0) break;
		long long mid = (rnd() | ((1ll * rnd()) << 31)) % sz;
		for (auto [r, k, l1, l2] : vec)
			if (mid >= l2 - l1 + 1) mid -= l2 - l1 + 1;
			else{
				Mmid = Msg3(l1 + mid, r, k);
				break;
			}
		if (check(Mmid)) Mr = Mmid;
		else Ml = Mmid;
	}
	ans = check(Ml) ? Ml : Mr;
	for (int i = 1; i <= n + lim; i++) cur[i] = 0;
	for (int i = ans.l; i <= ans.r; i++){
		int c = 0;
		for (int j = 0; j < lim; j++){
			c = c + ((a[i] >> j) & 1) + cur[i + j + ans.k];
			cur[i + j + ans.k] = c % 2;
			c /= 2;
		}
	}
	int i = n + lim;
	while (cur[i] == 0) i--;
	for (; i >= 0; i--) cout << cur[i];
	cout << endl;
}
int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//	freopen("in.txt", "r", stdin);
//	freopen("out.txt", "w", stdout);
	pw1[0] = pw2[0] = inv1[0] = inv2[0] = 1;
	for (int i = 1; i < N * 2; i++){
		pw1[i] = 2ll * pw1[i - 1] % mod1;
		pw2[i] = 2ll * pw2[i - 1] % mod2;
		inv1[i] = 1ll * inv1[i - 1] * ((mod1 + 1) / 2) % mod1;
		inv2[i] = 1ll * inv2[i - 1] * ((mod2 + 1) / 2) % mod2;
	}
	all1[1] = Msg(1, 1, 1);
	for (int i = 2; i < N; i++) all1[i] = all1[i - 1] + all1[1];
	cin >> tt;
	while (tt--) solve();
	return C;
}