#include <bits/stdc++.h>
using namespace std;
typedef __uint128_t I;
#define L(T) (T == 1 ? 10 : T == 2 ? 20 : 128)
int pigeon_num(int T, int k) {
	return 126 * (k + 1) + 3;
}

string send(int T, int n, int k, I msg) {
	string r;
	for (int i=0; i<=125; i++)
		r += string (k + 1, msg >> i & 1 ? '1' : '0');
	int c = msg >> 126;
	r += string (c, '1') + string (3 - c, '0');
	return r;
}

I receive(int T, int k, const string &msg) {
	I r = 0;
	int x[128]; string t = msg;
	for (int i=0; i<=125; i++) {
		x[i] = t[i*(k+1)] - '0';
		for (int j=i*(k+1)+1, p=j; j<(i+1)*(k+1); j++)
			if (t[j] ^ t[j-1]) {
				p = max(p, j);
				while (t[p] ^ t[j-1]) p ++;
				swap(t[j], t[p]);
			}
	}
	int c = t[126*(k+1)] - '0' + t[126*(k+1)+1] - '0' + t[126*(k+1)+2] - '0';
	x[126] = c & 1, x[127] = c >> 1;
	for (int i=127; ~i; i--)
		(r <<= 1) |= x[i];
	return r;
}