#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], pre[N], id[N];
int log2n, st[N][25];
int pre2[N];
ull sum[N][lim + 5];
int pw1[N * 2], pw2[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 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 askl1(int p, int l, int r, int s){
		if (a[p].msg.a1 == 0 && a[p].msg.a2 == 0) return 0;
		if (r <= s){
			if (l == r) return l;
			int res = askl1(a[p].rs, mid + 1, r, s);
			if (res) return res;
			else return askl1(a[p].ls, l, mid, s);
		}
		if (mid < s){
			int res = askl1(a[p].rs, mid + 1, r, s);
			if (res) return res;
			else return askl1(a[p].ls, l, mid, s);
		}else return askl1(a[p].ls, l, mid, s);
	}
	int askl0(int p, int l, int r, int s){
		if (same(a[p].msg, all1[r - l + 1])) return 0;
		if (r <= s){
			if (l == r) return l;
			int res = askl0(a[p].rs, mid + 1, r, s);
			if (res) return res;
			else return askl0(a[p].ls, l, mid, s);
		}
		if (mid < s){
			int res = askl0(a[p].rs, mid + 1, r, s);
			if (res) return res;
			else return askl0(a[p].ls, l, mid, s);
		}else return askl0(a[p].ls, l, mid, s);
	}
#undef mid
}T;
int lcp(int i, int j){
	int p1 = prehigh[i], p2 = prehigh[j];
	if (p1 < p2) swap(i, j), swap(p1, p2);
	int l = 1, r = min(p1, p2), mid;
	while (l <= r){
		mid = (l + r) >> 1;
		if (same(T.ask(rt[i], 1, n + lim, p1 - mid + 1, p1), T.ask(rt[j], 1, n + lim, p2 - mid + 1, p2))) l = mid + 1;
		else r = mid - 1;
	}
	if (r == p2 && p1 > p2){
		int p = T.askl1(rt[i], 1, n + lim, p1 - p2);
		return p ? r + (p1 - p2 - p) : inf;
	}else return r;
}
int lcp2(int i, int j){
	if (i == j) return prehigh[i];
	else{
		int l = min(id[i], id[j]), r = max(id[i], id[j]) - 1;
		int t = 31 ^ __builtin_clz(r - l + 1);
		return min({st[l][t], st[r - (1 << t) + 1][t], prehigh[i], prehigh[j]});
	}
}
template<typename T> int cmp(T a, T b){
	if (a > b) return 1;
	else if (a == b) return 0;
	else return -1;
}
int cmp_pre(int i, int j){
	int p1 = prehigh[i], p2 = prehigh[j];
	int r = lcp(i, j);
	int num1 = p1 <= r ? 0 : T.ask(rt[i], 1, n + lim, p1 - r).a1;
	int num2 = p2 <= r ? 0 : T.ask(rt[j], 1, n + lim, p2 - r).a1;
	return cmp(num1, num2);
}
struct Msg2{
	int tp, len, num, r;
	Msg2(){}
	Msg2(int tp, int len, int num, int r) : tp(tp), len(len), num(num), r(r) {}
};
unordered_map<int, pair<vector<Msg2>, int>> mp[N];
pair<vector<Msg2>, int> getMsg(int l, int r){
	//1 ~ l-1  l ~ l+lim-1  l+lim ~ p p+1 ~ prehigh[r1]
	pair<vector<Msg2>, int> &res = mp[l][r];
	if (res.second) return res;
	if (r - l <= lim){
		ull x = sum[r][r - l], bits = 63 ^ __builtin_clzll(x), ph = l + bits;
		if (bits >= lim) res = make_pair(vector<Msg2>{Msg2(0, lim, x & ((1 << lim) - 1), 0), Msg2(0, bits - lim + 1, x >> lim, 0)}, ph);
		else res = make_pair(vector<Msg2>{Msg2(0, bits + 1, x, 0)}, ph);
	}
	int a = T.ask(rt[r], 1, n + lim, l, l + lim - 1).a1, b = pre2[l];
	if (a >= b) res = make_pair(vector<Msg2>{Msg2(0, lim, a - b, 0), Msg2(2, prehigh[r] - (l + lim - 1), r, prehigh[r])}, prehigh[r]);
	else{
		int p = T.askr(rt[r], 1, n + lim, l + lim);
		if (p < prehigh[r]) res = make_pair(vector<Msg2>{Msg2(0, lim, (1 << lim) + a - b, 0), Msg2(1, p - (l + lim), 1, 0), Msg2(1, 1, 0, 0), Msg2(2, prehigh[r] - p, r, prehigh[r])}, prehigh[r]);
		else res = make_pair(vector<Msg2>{Msg2(0, lim, (1 << lim) + a - b, 0), Msg2(1, p - (l + lim), 1, 0)}, prehigh[r] - 1);
	}
	return res;
}
ull MR(ull x, int y){
	if (y >= 64) return 0;
	else return x >> y;
}
int C = 0;
int cmp_seg(int l1, int r1, int l2, int r2, int k){//left >> k 缩小 
	C++;
	int _lcp = lcp2(r1, r2);
	auto [vec1, ph1] = getMsg(l1, r1);
	auto [vec2, ph2] = getMsg(l2, r2);
	if (ph1 - k != ph2) return cmp(ph1 - k, ph2);
	{
		int len1 = ph1 - l1, len2 = ph2 - l2;
		if (len1 < len2) vec1.insert(vec1.begin(), Msg2(1, len2 - len1, 0, 0));
		else if (len1 > len2) vec2.insert(vec2.begin(), Msg2(1, len1 - len2, 0, 0));
	}
	if (vec1.back().tp == 2 && vec2.back().tp == 2 && _lcp < min(vec1.back().len, vec2.back().len))
		return cmp(T.ask(rt[r1], 1, n + lim, ph1 - _lcp).a1, T.ask(rt[r2], 1, n + lim, ph2 - _lcp).a1);
	while (!vec1.empty() && !vec2.empty()){
		Msg2 msg1 = vec1.back(), msg2 = vec2.back();
		vec1.pop_back(), vec2.pop_back();
		if (msg1.len == 0) vec2.push_back(msg2);
		else if (msg2.len == 0) vec1.push_back(msg1);
		else{
			int flg = 1;
			if (msg1.len < msg2.len){
				flg = -1;
				swap(msg1, msg2);
			}
			int len2 = msg1.len - msg2.len;
			Msg2 msg3;
			if (msg1.tp == 0){
				msg3 = Msg2(0, len2, msg1.num & ((1 << len2) - 1), 0);
				int num2;
				if (msg2.tp == 0) num2 = msg2.num;
				else if (msg2.tp == 1) num2 = msg2.num ? ((1 << msg2.len) - 1) : 0;
				else num2 = T.ask(rt[msg2.num], 1, n + lim, msg2.r - msg2.len + 1, msg2.r).a1;
				if ((msg1.num >> len2) != num2) return cmp(msg1.num >> len2, num2) * flg;
			}else if (msg1.tp == 1 && msg1.num == 0){
				msg3 = Msg2(1, len2, 0, 0);
				if (msg2.tp <= 1){
					if (msg2.num > 0) return -flg;
				}else{
					int pos = T.askl1(rt[msg2.num], 1, n + lim, msg2.r);
					if (msg2.r - pos < msg2.len) return -flg;
				}
			}else if (msg1.tp == 1 && msg1.num == 1){
				msg3 = Msg2(1, len2, 1, 0);
				if (msg2.tp == 0){
					if (msg2.num < ((1 << msg2.len) - 1)) return flg; 
				}else if (msg2.tp == 1){
					if (msg2.num == 0) return flg;
				}else{
					int pos = T.askl0(rt[msg2.num], 1, n + lim, msg2.r);
					if (msg2.r - pos < msg2.len) return flg;
				}
			}else{
				msg3 = Msg2(2, len2, msg1.num, msg1.r - msg2.len);
				if (msg2.tp == 0){
					int num2 = T.ask(rt[msg1.num], 1, n + lim, msg1.r - msg2.len + 1, msg1.r).a1;
					if (num2 != msg2.num) return cmp(num2, msg2.num) * flg;
				}else if (msg2.tp == 1){
					if (msg2.num == 0){
						int pos = T.askl1(rt[msg1.num], 1, n + lim, msg1.r);
						if (msg1.r - pos < msg2.len) return flg;
					}else{
						int pos = T.askl0(rt[msg1.num], 1, n + lim, msg1.r);
						if (msg1.r - pos < msg2.len) return -flg;
					}
				}
			}
			if (len2){
				if (flg == -1) vec2.push_back(msg3);
				else vec1.push_back(msg3);
			}
		}
	}
	return 0;
}
int cmp_seg(int l1, int r1, int l2, int r2, int k1, int k2){//left << k1 right << k2
	int k = k2 - k1;
	if (k >= 0) return cmp_seg(l1, r1, l2, r2, k);
	else return -cmp_seg(l2, r2, l1, r1, -k);
}
struct Msg3{
	int l, r, k;//放大 
	Msg3(){}
	Msg3(int l, int r, int k) : l(l), r(r), k(k) {}
	friend bool operator < (const Msg3 &a, const Msg3 &b){
		int res = cmp_seg(a.l, a.r, b.l, b.r, a.k, b.k);
		if (res == 0) return make_pair(a.l, a.r) < make_pair(b.l, b.r);
		else return res == -1;
	}
};
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){
	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 || cmp_seg(i, i, curans.l, curans.r, n - (i + j), curans.k) <= 0){
				while (i - rr <= lim && rr > 0 && cmp_seg(rr, i, curans.l, curans.r, n - (i + j), curans.k) <= 0) rr--;
				if (i - rr > lim){
					int l = 0, r = rr, mid;
					while (l <= r){
						mid = (l + r) >> 1;
						if (cmp_seg(mid + 1, i, curans.l, curans.r, n - (i + j), curans.k) <= 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;
		}
		pre[i] = i;
		pre2[i] = (pre2[i - 1] + a[i - 1]) / 2;
	}
	for (int i = 1; i <= n; i++){
		ull cur = 0;
		for (int j = i; j >= max(i - lim, 1); j--){
			cur = cur * 2 + a[j];
			sum[i][i - j] = cur;
		}
	}
	sort(pre + 1, pre + 1 + n, [&](int i, int j){return cmp_pre(i, j) == -1;});
	for (int i = 1; i <= n; i++) id[pre[i]] = i;
	log2n = log2(n);
	for (int i = 1; i < n; i++) st[i][0] = lcp(pre[i], pre[i + 1]);
	for (int j = 1; j <= log2n; j++)
		for (int i = 1; i + (1 << j) - 1 <= n; i++)
			st[i][j] = min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
	Msg3 Ml(1, 1, 0), Mr(1, n, n - 1), Mmid, ans;
	for (int i = 2; i <= n; i++)
		if (Msg3(i, i, 0) < Ml)
			Ml = Msg3(i, i, 0);
	while (1){
		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 && cmp_seg(Ml.l, Ml.r, r, i, Ml.k, n - (i + j)) != -1){
					int l2 = 1, r2 = r - 1, mid;
					while (l2 <= r2){
						mid = (l2 + r2) >> 1;
						if (cmp_seg(Ml.l, Ml.r, mid, i, Ml.k, n - (i + j)) == -1) l2 = mid + 1;
						else r2 = mid - 1;
					}
					r = r2;
				}
				if (l > 1 && cmp_seg(l - 1, i, Mr.l, Mr.r, n - (i + j), Mr.k) == -1){
					int l2 = 1, r2 = l - 1, mid;
					while (l2 <= r2){
						mid = (l2 + r2) >> 1;
						if (cmp_seg(mid, i, Mr.l, Mr.r, n - (i + j), Mr.k) == -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);
	all1[1] = Msg(1, 1, 1);
	for (int i = 2; i < N; i++) all1[i] = all1[i - 1] + all1[1];
	pw1[0] = pw2[0] = 1;
	for (int i = 1; i < N * 2; i++){
		pw1[i] = 2ll * pw1[i - 1] % mod1;
		pw2[i] = 2ll * pw2[i - 1] % mod2;
	}
	cin >> tt;
	while (tt--) solve();
	return 0;
}