Consider all binary strings of length $m$ ($1 \le m \le 60$). A binary string is a string that consists of the characters 0 and 1 only. For example, 0110 is a binary string, and 012aba is not. Obviously, there are exactly $2^m$ such strings in total.

The string $s$ is lexicographically smaller than the string $t$ (both have the same length $m$) if in the first position $i$ from the left in which they differ, we have $s[i] < t[i]$. This is exactly the way strings are compared in dictionaries and in most modern programming languages when comparing them in a standard way. For example, the string 01011 is lexicographically smaller than the string 01100, because the first two characters are the same, and the third character in the first string is less than that in the second.

We remove from this set $n$ ($1 \le n \le \min(2^m-1, 100)$) distinct binary strings $a_1, a_2, \ldots, a_n$, each of length $m$. Thus, the set will have $k=2^m-n$ strings. Sort all strings of the resulting set in lexicographical ascending order (as in the dictionary).

We number all the strings after sorting from $0$ to $k-1$. Print the string whose index is $\lfloor \frac{k-1}{2} \rfloor$ (such an element is called median), where $\lfloor x \rfloor$ is the rounding of the number down to the nearest integer.

For example, if $n=3$, $m=3$ and $a=[$010, 111, 001$]$, then after removing the strings $a_i$ and sorting, the result will take the form: $[$000, 011, 100, 101, 110$]$. Thus, the desired median is 100.


-----Input-----

The first line contains an integer $t$ ($1 \le t \le 1000$) — the number of test cases. Then, $t$ test cases follow.

The first line of each test case contains integers $n$ ($1 \le n \le \min(2^m-1, 100)$) and $m$ ($1 \le m \le 60$), where $n$ is the number of strings to remove, and $m$ is the length of binary strings. The next $n$ lines contain $a_1, a_2, \ldots, a_n$ — distinct binary strings of length $m$.

The total length of all given binary strings in all test cases in one test does not exceed $10^5$.


-----Output-----

Print $t$ answers to the test cases. For each test case, print a string of length $m$ — the median of the sorted sequence of remaining strings in the corresponding test case.


-----Example-----
Input
5
3 3
010
001
111
4 3
000
111
100
011
1 1
1
1 1
0
3 2
00
01
10

Output
100
010
0
1
11



-----Note-----

The first test case is explained in the statement.

In the second test case, the result after removing strings and sorting is $[$001, 010, 101, 110$]$. Therefore, the desired median is 010.

Difficulty: HARD
Tags: Complete search

Bit manipulation

Sorting

Constructive algorithms
Skill types: Bit manipulation

Sorting

Complete search

Starter code:

Solutions:
t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	median = (2 ** m - 1 - n) // 2
	a = [int(input(), 2) for i in range(n)]
	for i in sorted(a):
		if i <= median:
			median += 1
	y = bin(median)[2:]
	print('0' * (m - len(y)) + y)


def calc(numbers, newans, i):
	count = 0
	ansarr = ''.join([str(x) for x in newans])
	for num in numbers:
		if num[:i + 1] == ansarr:
			count += 1
	return count
t = int(input())
for _ in range(t):
	(n, m) = [int(c) for c in input().split()]
	numbers = []
	for i in range(n):
		numbers.append(input())
	ans = 0
	ansarr = []
	k = ((1 << m) - n - 1) // 2 + 1
	for i in range(m):
		nums = 1 << m - 1 - i
		newans = ans | 0
		remainums = nums - calc(numbers, ansarr + [0], i)
		if remainums < k:
			k -= remainums
			ansarr.append(1)
			newans = ans | 1 << m - i - 1
		else:
			ansarr.append(0)
			newans = ans | 0
		ans = newans
	print(''.join([str(c) for c in ansarr]))


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	arr = []
	for j in range(n):
		x = input()
		arr.append(int(x, 2))
	current_median = 2 ** (m - 1) - 1
	to_left = (2 ** m - n - 1) // 2 + 1
	while True:
		curr_to_left = current_median + 1
		present = False
		for j in arr:
			if j == current_median:
				present = True
			if j <= current_median:
				curr_to_left -= 1
		if curr_to_left == to_left and present == False:
			print(bin(current_median)[2:].zfill(m))
			break
		elif curr_to_left < to_left:
			current_median += 1
		else:
			current_median -= 1


T = int(input())

def move_up(taken, s):
	s += 1
	while s in taken:
		s += 1
	return s

def move_down(taken, s):
	s -= 1
	while s in taken:
		s -= 1
	return s
for t in range(T):
	(N, M) = [int(_) for _ in input().split()]
	start = (1 << M - 1) - 1
	taken = set()
	rd = True
	for i in range(N):
		el = int(input(), 2)
		taken.add(el)
		if el > start:
			if not rd:
				start = move_down(taken, start)
		elif el < start:
			if rd:
				start = move_up(taken, start)
		elif rd:
			start = move_up(taken, start)
		else:
			start = move_down(taken, start)
		rd = not rd
	print(format(start, '0{}b'.format(M)))


def dd(i, nn):
	s = bin(i).replace('0b', '')
	l = len(s)
	kk = ''
	for i in range(nn - l):
		kk = kk + '0'
	print(kk + s)
t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	aa = []
	for pp in range(n):
		pp = input()
		aa.append(int(pp, 2))
	y = 2 ** (m - 1) - 1
	a = max(0, y - n)
	b = min(y + n, 2 ** m - 1)
	for i in range(a, b + 1):
		l = i
		r = 2 ** m - 1 - i
		flag = 1
		for k in aa:
			if k == i:
				flag = 0
				break
			if k < i:
				l = l - 1
			else:
				r = r - 1
		if flag == 0:
			continue
		if n % 2 == 0 and l == r - 1:
			dd(i, m)
		if n % 2 != 0 and l == r:
			dd(i, m)


def check(ct, val, incre):
	while bin(val) in ct:
		val += incre
	return val
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	length = 2 ** m
	mid_index = (2 ** m - 1) // 2
	ct = set()
	for _ in range(n):
		res = bin(int(input(), 2))
		ct.add(res)
		if int(res, 2) < mid_index:
			length -= 1
			if length % 2:
				mid_index = check(ct, mid_index + 1, 1)
		elif int(res, 2) > mid_index:
			length -= 1
			if not length % 2:
				mid_index = check(ct, mid_index - 1, -1)
		else:
			length -= 1
			if not length % 2:
				mid_index = check(ct, mid_index - 1, -1)
			else:
				mid_index = check(ct, mid_index + 1, +1)
	diff = abs(m - len(str(bin(mid_index))[2:]))
	print('0' * diff + bin(mid_index)[2:])


import math as mt
import sys
import collections as cc
I = lambda : list(map(int, input().split()))
for tc in range(int(input())):
	used = cc.defaultdict(int)
	(n, m) = I()
	mid = 2 ** (m - 1) - 1
	k = 2 ** m
	for i in range(n):
		x = int(input(), 2)
		used[x] = 1
		if x == mid:
			if k % 2 == 0:
				t = mid + 1
				an = -1
				for ii in range(t, 2 ** m):
					if not used[ii]:
						an = ii
						break
				mid = an
			else:
				t = mid - 1
				an = -1
				for ii in range(t, -1, -1):
					if not used[ii]:
						an = ii
						break
				mid = an
		elif x < mid:
			if k % 2 == 0:
				t = mid + 1
				an = -1
				for ii in range(t, 2 ** m):
					if not used[ii]:
						an = ii
						break
				mid = an
			else:
				pass
		elif x > mid:
			if k % 2 == 0:
				pass
			else:
				t = mid - 1
				an = -1
				for ii in range(t, -1, -1):
					if not used[ii]:
						an = ii
						break
				mid = an
		k -= 1
	print(format(mid, '0' + str(m) + 'b'))


import bisect
T = int(input())
for _ in range(T):
	(N, M) = list(map(int, input().split()))
	aa = sorted([int(input(), 2) for _ in range(N)])
	K = 1 << M
	ans = 0
	for k in reversed(list(range(M))):
		tmp = ans + (1 << k)
		La = bisect.bisect_left(aa, tmp)
		Ra = N - La
		L = tmp - La
		R = K - tmp - Ra
		if L < R:
			ans = tmp
		else:
			continue
	print(f'{ans:0{M}b}')


import sys

def process():
	(n, m) = [int(s) for s in sys.stdin.readline().split()]
	med = (2 ** m - 1 - n) // 2
	ss = set()
	count = 0
	for i in range(n):
		r = int(sys.stdin.readline().strip(), 2)
		if r < med:
			count += 1
		else:
			ss.add(r)
	while med in ss:
		med += 1
	for i in range(count):
		med += 1
		while med in ss:
			med += 1
	print(format(med, 'b').zfill(m))
T = int(sys.stdin.readline())
for x in range(T):
	process()


def prog():
	for _ in range(int(input())):
		(n, m) = map(int, input().split())
		missing = [int(input().strip(), 2) for i in range(n)]
		missing.sort()
		missing2 = set(missing)
		median = (2 ** m - n + 1) // 2
		curr = median - 1
		index = median
		while curr in missing2:
			curr -= 1
			index -= 1
		for i in missing:
			if curr > i:
				index -= 1
			else:
				break
		while index != median:
			curr += 1
			if curr not in missing:
				index += 1
		value = curr
		value = bin(value)[2:]
		value = '0' * (m - len(value)) + value
		print(value)
prog()


from sys import stdin, stdout
import sys
from math import *

def c(m, a):
	mid = bin(a)[2:]
	mid = '0' * (m - len(mid)) + mid
	return mid
for __ in range(int(input())):
	(n, m) = map(int, input().split())
	mid = bin((2 ** m - 1) // 2)[2:]
	temp = (2 ** m - 1) // 2
	mid = '0' * (m - len(mid)) + mid
	d = {}
	p = 0
	a = 0
	ss = []
	for i in range(n):
		ss.append(input())
	ss.sort()
	for i in range(n):
		s = ss[i]
		if s < mid:
			p += 1
			d[s] = 1
		elif s > mid:
			a += 1
			d[s] = 1
		else:
			p += 1
			temp += 1
			mid = c(m, temp)
			d[s] = 1
	tot = 2 ** m - 1 - n
	smid = tot // 2
	curr = temp - p
	if curr < smid:
		while curr != smid:
			temp += 1
			if d.get(c(m, temp)) == None:
				curr += 1
				mid = c(m, temp)
	elif curr > smid:
		while curr != smid:
			temp -= 1
			if d.get(c(m, temp)) == None:
				curr -= 1
				mid = c(m, temp)
	print(mid)


import math
t = int(input())

def convert(s):
	new = ''
	for x in s:
		new += x
	return new
for i in range(t):
	(a, b) = map(int, input().split())
	removed = []
	for j in range(a):
		removed.append(int(input(), 2))
	removed.sort()
	pointer = 0
	leftcount = 0
	for j in range(2 ** (b - 1) - 101, 2 ** (b - 1) + 101):
		if pointer < a:
			while removed[pointer] < j:
				pointer += 1
				leftcount += 1
				if pointer == a:
					break
		if j + 1 - leftcount >= 2 ** b - j - 1 - (a - leftcount):
			if j in removed:
				continue
			s = '{0:b}'.format(j)
			ans = []
			for k in range(b - len(s)):
				ans.append('0')
			for k in range(len(s)):
				ans.append(s[k])
			print(convert(ans))
			break


from sys import stdin, stdout

def input():
	return stdin.readline()

def ans(n, m, l, f, low, high):
	for i in range(low, high + 1):
		mi = 0
		ma = 0
		for j in l:
			if j <= i:
				mi += 1
			if j > i:
				ma += 1
		rig = f - i - ma
		lef = i + 1 - mi
		if lef - rig == 1 or rig == lef:
			return i

def main():
	for _ in range(int(input())):
		(n, m) = map(int, input().split())
		f = 2 ** m - 1
		l = []
		for i in range(n):
			l.append(int(input().strip(), 2))
		med = 2 ** (m - 1) - 1
		if med - n // 2 - 1 < 0:
			low = 0
		else:
			low = med - n // 2 - 1
		if med + n // 2 + 1 > f - 1:
			high = f
		else:
			high = med + n // 2 + 1
		k = bin(ans(n, m, l, f, low, high))[2:]
		print('0' * (m - len(k)) + k)
main()


import sys
input = sys.stdin.readline
(T,) = map(int, input().split())
for _ in range(T):
	(N, M) = map(int, input().split())
	m = 2 ** (M - 1) - 1
	vs = set()
	for i in range(N):
		x = int(input(), 2)
		vs.add(x)
		if i % 2:
			if m <= x:
				while True:
					m -= 1
					if m not in vs:
						break
		elif x <= m:
			while True:
				m += 1
				if m not in vs:
					break
	print(format(m, '0{}b'.format(M)))


T = int(input())
for _ in range(T):
	(n, m) = input().split()
	n = int(n)
	m = int(m)
	li = []
	for i in range(n):
		temp = input()
		li.append(temp)
	li.sort()
	temp5 = (2 ** m - n - 1) // 2
	for i in range(n):
		if int(li[i], 2) <= temp5:
			temp5 += 1
		else:
			break
	temp6 = len(bin(temp5)[2:])
	ans = '0' * (m - temp6) + str(bin(temp5)[2:])
	print(ans)


import sys, heapq
from collections import *
from functools import lru_cache
sys.setrecursionlimit(10 ** 6)

def main():
	t = int(input())
	for _ in range(t):
		(n, m) = map(int, input().split(' '))
		total = 2 ** m
		mid = (total - 1) // 2
		removes = set()
		for _ in range(n):
			s = input()
			cur = 0
			for ch in s:
				cur = cur << 1
				if ch == '1':
					cur += 1
			removes.add(cur)
		removed = set()
		for r in removes:
			if total & 1 and r >= mid:
				while mid - 1 in removed:
					mid -= 1
				mid -= 1
			elif total & 1 == 0 and r <= mid:
				while mid + 1 in removed:
					mid += 1
				mid += 1
			total -= 1
			removed.add(r)
		res = []
		for i in range(m):
			if mid & 1 << i:
				res.append('1')
			else:
				res.append('0')
		print(''.join(res[::-1]))
main()


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import factorial, floor
from collections import Counter, defaultdict, deque
from heapq import heapify, heappop, heappush

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

def RLL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
	return int(input())

def comb(n, m):
	return factorial(n) / (factorial(m) * factorial(n - m)) if n >= m else 0

def perm(n, m):
	return factorial(n) // factorial(n - m) if n >= m else 0

def mdis(x1, y1, x2, y2):
	return abs(x1 - x2) + abs(y1 - y2)
mod = 998244353
INF = float('inf')
from bisect import bisect

def main():
	for _ in range(N()):
		(n, mm) = RL()
		arr = [int(input(), 2) for _ in range(n)]
		arr.sort()
		now = 2 ** mm - n
		res = (now - 1) // 2
		for i in arr:
			if i <= res:
				res += 1
		res = bin(res)[2:].zfill(mm)
		print(res)
main()


def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
import bisect

def solve(N, M, remove):
	remove = sorted(remove)
	K = 2 ** M - N
	index = (K - 1) // 2
	if index < remove[0]:
		return index
	for i in range(N):
		if i < N - 1:
			value = index + i + 1
			if value > remove[i] and value < remove[i + 1]:
				return value
			pass
		else:
			value = index + N
			if value > remove[-1]:
				return value
	pass
test_cases = inp()
for test in range(test_cases):
	(N, M) = inlt()
	remove = []
	for i in range(N):
		remove.append(int(input(), 2))
	output = bin(solve(N, M, remove))[2:]
	length = len(output)
	print(output.zfill(M))


import sys
input = sys.stdin.readline
from collections import *
from bisect import *

def judge(x):
	return b[x] - x >= C

def binary_search():
	(l, r) = (0, len(b) - 1)
	while l <= r:
		m = (l + r) // 2
		if judge(m):
			r = m - 1
		else:
			l = m + 1
	return l
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	b = []
	for _ in range(n):
		a = input()[:-1]
		a = a[::-1]
		c = 0
		for i in range(m):
			if a[i] == '1':
				c += 2 ** i
		b.append(c)
	b.append(2 ** m)
	b.sort()
	C = (2 ** m - n + 1) // 2
	X = binary_search()
	diff = b[X] - X - C
	x = b[X] - diff - 1
	ans = []
	for i in range(m):
		if x >> i & 1:
			ans.append('1')
		else:
			ans.append('0')
	ans.reverse()
	print(''.join(ans))


def binaryToDecimal(x):
	return int(x) if len(x) <= 1 else binaryToDecimal(x[:-1]) * 2 + int(x[-1])

def decimalToBinary(m, x):
	if x == 0:
		return '0' * m
	res = ''
	while x > 0:
		res = str(x % 2) + res
		x //= 2
	while len(res) < m:
		res = '0' + res
	return res

def upperBound(a, x):
	l = 0
	r = len(a) - 1
	res = -1
	while l <= r:
		mid = (l + r) // 2
		if a[mid] <= x:
			res = mid
			l = mid + 1
		else:
			r = mid - 1
	return 0 if res == -1 else res + 1

def lowerBound(a, x):
	l = 0
	r = len(a) - 1
	res = -1
	while l <= r:
		mid = (l + r) // 2
		if a[mid] >= x:
			res = mid
			r = mid - 1
		else:
			l = mid + 1
	return 0 if res == -1 else len(a) - res
t = int(input())
for i in range(t):
	(n, m) = [int(i) for i in input().split()]
	a = [binaryToDecimal(input()) for j in range(n)]
	a.sort()
	l = 0
	r = 2 ** m - 1
	res = 0
	key = 0 if n % 2 == 1 else -1
	while l <= r:
		mid = (l + r) // 2
		t1 = 0 if mid == 0 else mid - upperBound(a, mid - 1)
		t2 = 0 if mid == 2 ** m - 1 else 2 ** m - mid - 1 - lowerBound(a, mid + 1)
		if t1 - t2 == key:
			res = mid
			break
		elif t1 - t2 > key:
			r = mid - 1
		else:
			l = mid + 1
	print(decimalToBinary(m, res))


def cast(now):
	if now == 0:
		return ''
	return cast(now // 2) + str(now % 2)

def is_mediana(all_numbers, num, a):
	if num in a:
		return False
	left = num
	right = all_numbers - num - 1
	for i in a:
		if i < num:
			left -= 1
		else:
			right -= 1
	return left == right or left + 1 == right
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = [int(input(), 2) for i in range(n)]
	now = (2 ** m - n - 1) // 2
	for i in range(100):
		if now - i >= 0 and is_mediana(2 ** m, now - i, a):
			ans = cast(now - i)
			ans = '0' * (m - len(ans)) + ans
			print(ans)
			break
		elif now + i < 2 ** m and is_mediana(2 ** m, now + i, a):
			ans = cast(now + i)
			ans = '0' * (m - len(ans)) + ans
			print(ans)
			break


from collections import deque
from sys import stdin, stdout
from string import ascii_letters
input = stdin.readline
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	lim = 2 ** m
	medium = (lim - 1) // 2
	was = {}
	for i in range(n):
		x = int(input().strip(), 2)
		was[x] = 1
		if (lim - (i + 1)) % 2 != 0:
			if x <= medium:
				medium += 1
				while medium in was:
					medium += 1
				if medium > lim:
					medium -= 1
					while medium in was:
						medium -= 1
		elif x >= medium:
			medium -= 1
			while medium in was:
				medium -= 1
			if medium < 0:
				medium += 1
				while medium in was:
					medium += 1
	res = '{0:b}'.format(medium)
	print('0' * (m - len(res)) + res)


from sys import stdin, stdout
import math
from bisect import bisect_left

def main():
	t = int(stdin.readline())
	for _ in range(t):
		(n, m) = list(map(int, stdin.readline().split()))
		total = pow(2, m) - 1
		med = math.floor(total / 2)
		arr = []
		for _ in range(n):
			num = int(stdin.readline(), 2)
			arr.append(num)
		arr.sort()
		ite = min(total + 1, 200)
		ans = 0
		for x in range(max(0, med - int(ite / 2)), min(total + 1, med + int(ite / 2) + 1)):
			pos = bisect_left(arr, x)
			if pos != len(arr) and arr[pos] == x:
				continue
			elif n % 2 == 1:
				left = x - pos
				right = total - x - (n - pos)
				if left == right:
					ans = x
					break
			else:
				left = x - pos + 1
				right = total - x - (n - pos)
				if left == right:
					ans = x
					break
		ans = bin(ans).replace('0b', '')
		if len(ans) < m:
			ans = '0' * (m - len(ans)) + ans
		stdout.write(ans + '\n')
main()


def add(s):
	b = []
	carry = 1
	for i in range(len(s) - 1, -1, -1):
		if carry == 0:
			cur = s[i]
		elif s[i] == '0':
			cur = '1'
			carry = 0
		else:
			cur = '0'
		b.append(cur)
	res = ''.join(b)[::-1]
	return res

def sub(s):
	b = []
	if s[-1] == '1':
		cur = '0'
		carry = 0
	else:
		cur = '1'
		carry = 1
	b.append(cur)
	for i in range(len(s) - 2, -1, -1):
		if carry == 0:
			cur = s[i]
		elif s[i] == '1':
			cur = '0'
			carry = 0
		else:
			cur = '1'
			carry = 1
		b.append(cur)
	res = ''.join(b)[::-1]
	return res

def update(x, func, b):
	x = func(x)
	while x in b:
		x = func(x)
	return x
T = int(input())
for _ in range(T):
	(n, m) = list(map(int, input().split()))
	a = [input() for _ in range(n)]
	ans = '0' + '1' * (m - 1)
	b = set()
	k = 0
	for (i, x) in enumerate(a):
		if x < ans:
			if k == 0:
				ans = update(ans, add, b)
		elif x > ans:
			if k == 1:
				ans = update(ans, sub, b)
		elif x == ans:
			if k == 0:
				ans = update(ans, add, b)
			else:
				ans = update(ans, sub, b)
		k = (k + 1) % 2
		b.add(x)
	print(ans)


def main():
	import sys
	input = sys.stdin.readline
	for __ in [0] * int(input()):
		(n, m) = map(int, input().split())
		A = [int(input(), 2) for _ in [0] * n]
		mid = (1 << m - 1) - 1
		L = set(range(max(0, mid - 120), min(mid + 121, 1 << m)))
		pari = 0
		for a in A:
			if a in L:
				L.remove(a)
			if a < mid:
				if pari == 0:
					mid += 1
					while mid not in L:
						mid += 1
				else:
					pass
			elif a > mid:
				if pari == 0:
					pass
				else:
					mid -= 1
					while mid not in L:
						mid -= 1
			elif a == mid:
				if pari == 0:
					mid += 1
					while mid not in L:
						mid += 1
				else:
					mid -= 1
					while mid not in L:
						mid -= 1
			pari ^= 1
		print(('0' * 60 + bin(mid)[2:])[-m:])
main()


TC = int(input())
for t_itr in range(TC):
	(N, M) = map(int, input().rstrip().split())
	A = []
	for _ in range(N):
		r = 0
		for x in map(int, input()):
			r = r * 2 + x
		A.append(r)
	A.sort()
	mid = (2 ** M - 1 - N) // 2
	for a in A:
		if a <= mid:
			mid += 1
	print('{{:0>{}b}}'.format(M).format(mid))


import bisect
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	ban = []
	for i in range(n):
		a = input()
		ban.append(int(a, 2))
	ban.sort()
	k = 2 ** m - n
	start = 0
	end = 2 ** m

	def func(num):
		res = num
		index = bisect.bisect_left(ban, num)
		res -= index
		return res
	while end - start > 1:
		test = (end + start) // 2
		if (k - 1) // 2 >= func(test):
			start = test
		else:
			end = test
	if (k - 1) // 2 >= func(end):
		ans = end
	else:
		ans = start
	ban = set(ban)
	while ans in ban:
		ans -= 1
	res = bin(ans)[2:]
	res = '0' * (m - len(res)) + res
	print(res)


import os
os_input = os.read(0, int(10000000.0)).split()
os_input_pos = -1

def cin():
	global os_input_pos
	os_input_pos += 1
	return os_input[os_input_pos]
from bisect import bisect
T = int(cin())
res = []
while T:
	T -= 1
	(n, m) = (int(cin()), int(cin()))
	ans = (2 ** m - 1) // 2
	a = sorted([int(cin(), 2) for i in range(n)])
	leq = bisect(a, ans)
	small = ans + 1 - leq
	big = 2 ** m - 1 - ans - (n - leq)
	have = set(a)
	while small > big:
		if ans not in have:
			small -= 1
			big += 1
		ans -= 1
	while small < big:
		ans += 1
		if ans not in have:
			small += 1
			big -= 1
	while ans in have:
		ans -= 1
	res.append(bin(ans)[2:].zfill(m))
os.write(1, '\n'.join(res).encode())


import sys
input = lambda : sys.stdin.readline().strip()

def solve():
	(n, m) = map(int, input().split())
	a = []
	for i in range(n):
		a.append(int(input(), 2))
	need = ((1 << m) - n - 1) // 2 + 1
	cur = (1 << m - 1) - 1
	while True:
		left = cur + 1
		flag = False
		for i in range(n):
			flag |= a[i] == cur
			if a[i] <= cur:
				left -= 1
		if left == need and (not flag):
			ans = bin(cur)[2:]
			print('0' * (m - len(ans)) + ans)
			return
		elif left < need:
			cur += 1
		else:
			cur -= 1
t = int(input())
while t:
	t -= 1
	solve()


from bisect import bisect_left, bisect_right

def solve():
	(n, m) = map(int, input().split())
	que = [int(input(), 2) for _ in range(n)]
	K = 2 ** m - n
	ban_set = set(que)
	que.sort()

	def count(X):
		return X + 1 - bisect_right(que, X)
	l = -1
	r = 2 ** m
	while r - l > 1:
		Med = (r + l) // 2
		if count(Med) >= (K + 1) // 2:
			r = Med
		else:
			l = Med
	while r in ban_set:
		r -= 1
	print(bin(r)[2:].zfill(m))
	return

def main():
	t = int(input())
	for i in range(t):
		solve()
	return
main()


def search(array, x):
	l = len(array)
	for i in range(l):
		if array[i] == x:
			return True
	return False

def binarySearch(array, l, r, x):
	while l <= r:
		m = (l + r) // 2
		if array[m] == x:
			return m
		elif array[m] > x:
			r = m - 1
		else:
			l = m + 1
t = int(input())
for i in range(t):
	(n, m) = list(map(int, input().split()))
	arr = []
	number = 2 ** m // 2 - 1
	for j in range(n):
		s = str(input())
		arr.append(s)
	num1 = []
	for j in range(n):
		s = 0
		for k in range(1, m + 1):
			s += int(arr[j][-k]) * 2 ** (k - 1)
		num1.append(s)
	c = 1
	for j in range(n):
		if num1[j] < number:
			if c == 1:
				number += 1
				while search(num1[:j], number) == True:
					number += 1
				c = 0
			else:
				c = 1
		if num1[j] > number:
			if c == 1:
				c = 0
			else:
				number -= 1
				while search(num1[:j], number) == True:
					number -= 1
				c = 1
		if num1[j] == number:
			if c == 0:
				number -= 1
				while search(num1[:j], number) == True:
					number -= 1
				c = 1
			else:
				number += 1
				while search(num1[:j], number) == True:
					number += 1
				c = 0
	ans = bin(number)
	ans = ans[2:]
	len2 = len(ans)
	s = ''
	for j in range(m - len2):
		s += '0'
	print(s + ans)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	arr = []
	for i in range(n):
		arr.append(input().strip())
	arr1 = []
	for i in arr:
		arr1.append(int(i, 2))
	a = (2 ** m - n - 1) // 2
	arr1.sort()
	for i in arr1:
		if i <= a:
			a += 1
	ans = bin(a).replace('0b', '')
	ans = '0' * (m - len(ans)) + ans
	print(ans)


tc = int(input())
for _ in range(tc):
	(n, m) = map(int, input().split())
	cache = {}
	curr = (2 ** m - 1) // 2
	for i in range(n):
		s = input()
		x = int(s, 2)
		cache[x] = 1
		if i % 2 == 0:
			if x <= curr:
				while len(cache) != 0 and curr + 1 in cache:
					curr += 1
				curr += 1
		elif x >= curr:
			while len(cache) != 0 and curr - 1 in cache:
				curr -= 1
			curr -= 1
	temp = bin(curr)[2:]
	if m != len(temp):
		temp = '0' * abs(m - len(temp)) + temp
	print(temp)


from bisect import *
import sys
sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.readline())

def MI():
	return map(int, sys.stdin.readline().split())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def SI():
	return sys.stdin.readline()[:-1]

def main():
	for _ in range(II()):
		(n, m) = MI()
		isrem = set()
		rem = []
		for _ in range(n):
			a = int(SI(), 2)
			rem.append(a)
			isrem.add(a)
		rem.sort()
		k = (1 << m) - n
		rank = (k - 1) // 2
		ans = rank
		while 1:
			while ans in isrem:
				ans += 1
			rn = bisect(rem, ans)
			if ans - rn == rank:
				break
			ans = rank + rn
		print(format(ans, 'b').zfill(m))
main()


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	k = 2 ** m - n
	l = [-1]
	for i in range(n):
		s = input()[::-1]
		c = 0
		for j in range(m):
			if s[j] == '1':
				c += pow(2, j)
		l.append(c)
	l.sort()
	l.append(2 ** m)
	count = (k + 1) // 2
	for i in range(1, n + 2):
		dif = l[i] - l[i - 1] - 1
		if dif < count:
			count -= dif
		else:
			ans = l[i - 1] + count
			break
	ans = bin(ans)[2:]
	print(ans.zfill(m))


import sys
import math
from collections import defaultdict, deque

def bintonum(s):
	ans = 0
	n = len(s)
	for i in range(n):
		ans = ans << 1
		ans = ans + int(s[i])
	return ans
t = int(sys.stdin.readline())
for _ in range(t):
	(n, m) = map(int, sys.stdin.readline().split())
	rem = []
	for i in range(n):
		s = sys.stdin.readline()[:-1]
		rem.append(bintonum(s))
	arr = [[0, pow(2, m) - 1]]
	for i in range(n):
		newarr = []
		k = len(arr)
		x = rem[i]
		for j in range(k):
			if arr[j][0] <= x <= arr[j][1]:
				if arr[j][0] != x:
					newarr.append([arr[j][0], x - 1])
				if x != arr[j][1]:
					newarr.append([x + 1, arr[j][1]])
			else:
				newarr.append([arr[j][0], arr[j][1]])
		arr = [y for y in newarr]
	median = (pow(2, m) - n - 1) // 2 + 1
	cnt = 0
	ans = 0
	k = len(arr)
	for i in range(k):
		x = arr[i][1] - arr[i][0] + 1
		if median <= x:
			ans = arr[i][0] + median - 1
			break
		else:
			median -= x
	res = bin(ans)[2:]
	y = len(res)
	res = '0' * (m - y) + res
	print(res)


import collections
import time
import os
import sys
import bisect
import heapq
from typing import List

def solve(bits, remove):
	(lo, hi) = (0, (1 << bits) - 1)
	half = ((1 << bits) - len(remove) + 1) // 2
	while lo <= hi:
		m = (lo + hi) // 2
		left = m + 1 - len([v for v in remove if v <= m])
		if left == half:
			while m >= 0:
				if m not in remove:
					return m
				m -= 1
			return m
		elif left > half:
			hi = m - 1
		else:
			lo = m + 1
	return 0
T = int(input())
ans = []
for i in range(T):
	(N, M) = map(int, input().split())
	remove = set()
	for i in range(N):
		remove.add(int(input(), 2))
	v = solve(M, remove)
	v = bin(v)[2:]
	v = '0' * (M - len(v)) + v
	ans.append(v)
print('\n'.join(ans))


import sys
input = sys.stdin.readline
t = int(input())
for tests in range(t):
	(n, m) = list(map(int, input().split()))
	A = sorted([int(input().strip(), 2) for i in range(n)])
	A += [1 << 63]
	ind = (2 ** m - n - 1) // 2
	indskip = 0
	ANS = 0
	while True:
		if A[indskip] == ANS:
			ANS += 1
			indskip += 1
			continue
		if A[indskip] - ANS <= ind:
			ind -= A[indskip] - ANS
			ANS = A[indskip] + 1
			indskip += 1
		else:
			ANS += ind
			break
	print(bin(ANS)[2:].zfill(m))


def cvt(st):
	st = st[::-1]
	num = 0
	for (i, ix) in enumerate(st):
		num += int(int(ix) * int(2 ** i))
	return num
for _ in range(int(input())):
	(n, m) = [int(i) for i in input().split()]
	maxx = 2 ** m - 1
	ran = maxx + 1
	med = maxx // 2
	rem = set()
	num = maxx + 1
	for i in range(n):
		if (ran - i) % 2 == 0:
			st = input()
			st = cvt(st)
			if st <= med:
				med += 1
				while med in rem:
					med += 1
			rem.add(st)
		else:
			st = input()
			st = cvt(st)
			if st >= med:
				med -= 1
				while med in rem:
					med -= 1
			rem.add(st)
	ans = [0 for i in range(m)]
	i = 0
	while med > 0:
		if med % 2 == 1:
			ans[i] = 1
		else:
			ans[i] = 0
		i += 1
		med //= 2
	a = ''
	for i in ans:
		a += str(i)
	print(a[::-1])


from sys import stdin, stdout
for _ in range(int(stdin.readline())):
	(n, m) = map(int, stdin.readline().split())
	median = (2 ** m - n - 1) // 2
	countless = 0
	countlarge = 0
	arr = [int(stdin.readline(), 2) for i in range(n)]
	arr.sort()
	for i in arr:
		if i <= median:
			median += 1
	median = bin(median)[2:]
	if m > len(median):
		stdout.write('0' * (m - len(median)) + median + '\n')
	else:
		stdout.write(median + '\n')


import sys, math, os
from io import BytesIO, IOBase
from bisect import bisect_left as bl, bisect_right as br, insort
from collections import defaultdict as dd, deque, Counter

def data():
	return sys.stdin.readline().strip()

def mdata():
	return list(map(int, data().split()))

def outl(var):
	sys.stdout.write(' '.join(map(str, var)) + '\n')

def out(var):
	sys.stdout.write(str(var) + '\n')
sys.setrecursionlimit(100000)
INF = float('inf')
mod = int(1000000000.0) + 7

def main():
	for t in range(int(data())):
		(n, m) = mdata()
		A = []
		for i in range(n):
			A.append(int(data(), 2))
		A.sort()
		k = (2 ** m - n - 1) // 2
		k1 = k
		while True:
			a = br(A, k1)
			if a != n and A[a] == k1:
				k1 += 1
				continue
			if k1 - a == k:
				break
			k1 += 1
		ans = bin(k1)[2:]
		ans = '0' * (m - len(ans)) + ans
		print(ans)
main()


from bisect import bisect_left, bisect_right

class Result:

	def __init__(self, index, value):
		self.index = index
		self.value = value

class BinarySearch:

	def __init__(self):
		pass

	@staticmethod
	def greater_than(num: int, func, size: int=1):
		if isinstance(func, list):
			index = bisect_right(func, num)
			if index == len(func):
				return Result(None, None)
			else:
				return Result(index, func[index])
		else:
			(alpha, omega) = (0, size - 1)
			if func(omega) <= num:
				return Result(None, None)
			while alpha < omega:
				if func(alpha) > num:
					return Result(alpha, func(alpha))
				if omega == alpha + 1:
					return Result(omega, func(omega))
				mid = (alpha + omega) // 2
				if func(mid) > num:
					omega = mid
				else:
					alpha = mid

	@staticmethod
	def less_than(num: int, func, size: int=1):
		if isinstance(func, list):
			index = bisect_left(func, num) - 1
			if index == -1:
				return Result(None, None)
			else:
				return Result(index, func[index])
		else:
			(alpha, omega) = (0, size - 1)
			if func(alpha) >= num:
				return Result(None, None)
			while alpha < omega:
				if func(omega) < num:
					return Result(omega, func(omega))
				if omega == alpha + 1:
					return Result(alpha, func(alpha))
				mid = (alpha + omega) // 2
				if func(mid) < num:
					alpha = mid
				else:
					omega = mid
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import gcd, ceil

def prod(a, mod=10 ** 9 + 7):
	ans = 1
	for each in a:
		ans = ans * each % mod
	return ans

def lcm(a, b):
	return a * b // gcd(a, b)

def binary(x, length=16):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y
bs = BinarySearch()
for _ in range(int(input()) if True else 1):
	(n, m) = map(int, input().split())
	total = 2 ** m - n
	a = []
	for i in range(n):
		next = int(input(), 2)
		a += [next]
	a = sorted(a)

	def f(x, comp=0):
		total = bs.less_than(x + 1, a).index
		if total is None:
			total = -1
		total += 1
		if total == comp:
			return x
		else:
			return f(x + total - comp, total)
	ans = bin(f((total - 1) // 2))[2:]
	print('0' * (m - len(ans)) + ans)


import sys
from math import ceil

def input():
	return sys.stdin.readline()[:-1]

def main():
	for _ in range(int(input())):
		(n, m) = map(int, input().split())
		l = [input() for k in range(n)]
		med = 2 ** (m - 1) - 1
		find = (2 ** m - n - 1) // 2
		while True:
			lower = med
			f = 0
			for e in l:
				if int(e, 2) < med:
					lower -= 1
				elif int(e, 2) == med:
					f = 1
			if lower < find or (lower == find and f):
				med += 1
			elif lower > find:
				med -= 1
			else:
				print(bin(med)[2:].zfill(m))
				break
main()


def solve():
	(n, m) = [int(x) for x in input().split()]
	a = []
	for i in range(n):
		a.append(input())
	a = [int(x, 2) for x in a]
	need = ((1 << m) - n - 1) // 2 + 1
	cur = (1 << m - 1) - 1
	while True:
		left = cur + 1
		flag = bool(cur in a)
		for s in a:
			if s <= cur:
				left -= 1
		if left == need and (not flag):
			ans = bin(cur).split('b')[1]
			if len(ans) < m:
				ans = '0' * (m - len(ans)) + ans
			print(ans)
			return
		elif left < need:
			cur += 1
		else:
			cur -= 1
t = int(input())
while t > 0:
	t -= 1
	solve()


import math

def binaryToDecimal(n):
	return int(n, 2)

def decimalToBinary(n, k):
	return '{0:b}'.format(n).zfill(k)

def main():
	t = int(input())
	for i in range(t):
		solve()

def solve():
	(n, m) = list(map(int, input().split(' ')))
	if m == 1:
		print((int(input()) + 1) % 2)
		return
	binaries = set()
	middle = (2 ** m - 1) // 2
	size = 2 ** m
	for i in range(n):
		current = binaryToDecimal(input())
		binaries.add(current)
		size -= 1
		if size % 2 == 0:
			if current >= middle:
				middle -= 1
				while middle in binaries:
					middle -= 1
		elif current <= middle:
			middle += 1
			while middle in binaries:
				middle += 1
	print(decimalToBinary(middle, m))
main()


import sys
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right
from collections import deque
from collections import Counter
from itertools import accumulate, combinations, permutations
from heapq import heapify, heappop, heappush
from functools import lru_cache

def input():
	return sys.stdin.readline()[:-1]

def printl(li):
	_ = print(*li, sep='\n') if li else None

def argsort(s, return_sorted=False):
	inds = sorted(range(len(s)), key=lambda k: s[k])
	if return_sorted:
		return (inds, [s[i] for i in inds])
	return inds

def alp2num(c, cap=False):
	return ord(c) - 97 if not cap else ord(c) - 65

def num2alp(i, cap=False):
	return chr(i + 97) if not cap else chr(i + 65)

def matmat(A, B):
	(K, N, M) = (len(B), len(A), len(B[0]))
	return [[sum([A[i][k] * B[k][j] for k in range(K)]) for j in range(M)] for i in range(N)]

def matvec(M, v):
	(N, size) = (len(v), len(M))
	return [sum([M[i][j] * v[j] for j in range(N)]) for i in range(size)]

def T(M):
	(n, m) = (len(M), len(M[0]))
	return [[M[j][i] for j in range(n)] for i in range(m)]

def main():
	mod = 1000000007
	(n, m) = map(int, input().split())
	ns = [int(input(), 2) for _ in range(n)]
	ns.sort()
	maxval = 2 ** m - 1
	k = maxval + 1 - n
	target = (k - 1) // 2
	left = -1
	right = maxval + 1

	def f(val):
		return val - bisect_right(ns, val) < target
	while right - left > 1:
		mid = (right + left) // 2
		if f(mid):
			left = mid
		else:
			right = mid
	print(format(left + 1, '0' + str(m) + 'b'))
q = int(input())
for _ in range(q):
	main()


def b_n(s):
	return int(s, 2)

def n_b(n):
	p = str(bin(n).replace('0b', ''))
	while len(p) < m:
		p = '0' + p
	return p
t = int(input())
for w in range(t):
	nm = list(map(int, input().strip().split()))
	n = nm[0]
	m = nm[1]
	arr = []
	for g in range(n):
		arr.append(str(input()))
	for i in range(n):
		arr[i] = b_n(arr[i])
	k1 = 2 ** m - n
	k = (k1 - 1) // 2
	for i in sorted(arr):
		if i <= k:
			k += 1
	print(n_b(k))


from bisect import *
t = int(input())

def solve(a, m):
	a = sorted(list(a))
	L = 0
	R = (1 << m) - 1
	target = ((1 << m) - len(a) - 1) // 2
	while R - L > 0:
		M = (L + R) // 2
		cntsmalleq = M - bisect_right(a, M, 0, len(a))
		if cntsmalleq < target:
			L = M + 1
		else:
			R = M
	return L
for _ in range(t):
	(n, m) = map(int, input().split())
	print(format(solve(map(lambda x: int(x, 2), [input() for _ in range(n)]), m), '0' + str(m) + 'b'))


def solve(n, m, remove):
	(l, r) = (0, 2 ** m - 1)
	k = 2 ** m - n
	target = (k - 1) // 2
	while l < r - 1:
		mid = (l + r) // 2
		c = mid + 1 - sum((x <= mid for x in remove))
		if c - 1 >= target:
			r = mid
		else:
			l = mid
	c1 = l + 1 - sum((x <= l for x in remove))
	if c1 - 1 == target and l not in remove:
		print(('{0:0%db}' % m).format(l))
	else:
		print(('{0:0%db}' % m).format(r))
	return
t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	remove = []
	for j in range(0, n):
		remove.append(int(input(), 2))
	solve(n, m, remove)


from bisect import bisect_left

def less_than(mid):
	ind = bisect_left(arr, mid)
	return mid - ind
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	arr = []
	a = set()
	for i in range(n):
		arr.append(int(input(), 2))
		a.add(arr[-1])
	arr.sort()
	total = 2 ** m - n
	l = 0
	r = 2 ** m - 1
	while l <= r:
		mid = l + (r - l) // 2
		l_mid = less_than(mid)
		if mid not in a and 0 <= total - 2 * l_mid - 1 <= 1:
			print(bin(mid)[2:].zfill(m))
			break
		elif l_mid >= total - l_mid:
			r = mid - 1
		else:
			l = mid + 1


production = True
import sys, math, collections

def input(input_format=0, multi=0):
	if multi > 0:
		return [input(input_format) for i in range(multi)]
	else:
		next_line = sys.stdin.readline()[:-1]
		if input_format >= 10:
			use_list = False
			input_format = int(str(input_format)[-1])
		else:
			use_list = True
		if input_format == 0:
			formatted_input = [next_line]
		elif input_format == 1:
			formatted_input = list(map(int, next_line.split()))
		elif input_format == 2:
			formatted_input = list(map(float, next_line.split()))
		elif input_format == 3:
			formatted_input = list(next_line)
		elif input_format == 4:
			formatted_input = list(map(int, list(next_line)))
		elif input_format == 5:
			formatted_input = next_line.split()
		else:
			formatted_input = [next_line]
		return formatted_input if use_list else formatted_input[0]

def out(output_line, output_format=0, newline=True):
	formatted_output = ''
	if output_format == 0:
		formatted_output = str(output_line)
	elif output_format == 1:
		formatted_output = ' '.join(map(str, output_line))
	elif output_format == 2:
		formatted_output = '\n'.join(map(str, output_line))
	print(formatted_output, end='\n' if newline else '')

def log(*args):
	if not production:
		print('$$$', end='')
		print(args)
enu = enumerate
ter = lambda a, b, c: b if a else c

def mapl(iterable, format=0):
	if format == 0:
		return list(map(int, iterable))
	elif format == 1:
		return list(map(str, iterable))
	elif format == 2:
		return list(map(list, iterable))

def solve():
	(n, m) = input(1)
	s = [int(x, 2) for x in input(10, n)]
	log(s)
	xd = 2 ** m
	md = xd - 1 >> 1
	ld = md - 200
	rd = md + 200
	xld = 0
	xrd = 0
	p = set()
	y = ld >= 0
	for i in s:
		if y:
			if i < ld:
				xld += 1
			elif i > rd:
				xrd += 1
			else:
				p.add(i)
		else:
			p.add(i)
	u = xd - n + 1 >> 1
	if y:
		c = ld - xld
	else:
		c = 0
		ld = 0
	log(p, u)
	for i in range(ld, rd):
		if c == u:
			out(bin(i - 1)[2:].zfill(m))
			break
		if i in p:
			continue
		else:
			c += 1
		log(i, c)
	return
for i in range(input(11)):
	solve()


def toBinary(i, digit):
	b = bin(i).replace('0b', '')
	n = digit - len(b)
	x = ''
	for itr in range(n):
		x = x + '0'
	return x + b

def main():
	t = int(input())
	for _ in range(t):
		(n, m) = map(int, input().split())
		l = []
		for i in range(n):
			l.append(int(input(), 2))
		l.sort()
		median = (2 ** m - n - 1) // 2
		for i in l:
			if i <= median or i == median:
				median += 1
		ans = toBinary(median, m)
		print(ans)
main()


from collections import defaultdict

def decimalToBinary(n, s):
	if n > 1:
		s = decimalToBinary(n // 2, s)
	s = s + str(n % 2)
	return s
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split(' '))
	arr = []
	for i in range(n):
		s = input()
		k = m - 1
		c = 0
		for j in s:
			c += int(j) * 2 ** k
			k -= 1
		arr.append(c)
	x = 2 ** m - n
	if x % 2 == 0:
		x = x // 2 - 1
	else:
		x = x // 2
	d = {}
	d = defaultdict(lambda : 0, d)
	for i in arr:
		d[i] = 1
	arr.sort()
	k = 0
	for i in arr:
		if i <= x:
			k += 1
		else:
			break
	i = 0
	j = x + 1
	y = 2 ** m
	ans = x
	while j < y:
		if i >= k:
			break
		if d[j] == 0:
			i += 1
			ans = j
		j += 1
	ans = decimalToBinary(ans, '')
	ans = '0' * (m - len(ans)) + ans
	print(ans)


def main():
	for t in range(int(input())):
		(n, m) = map(int, input().split())
		l = []
		for i in range(n):
			l.append(int(input(), 2))
		l.sort()
		median = (2 ** m - n - 1) // 2
		for i in l:
			if i <= median:
				median += 1
		while median in l:
			median += 1
		ans = bin(median)[2:]
		temp = ''
		for i in range(len(ans), m):
			temp += '0'
		print(temp + ans)
main()


import os
import sys
from io import BytesIO, IOBase

def iin():
	return int(input())

def lin():
	return list(map(int, input().split()))

def main():

	def normalize(m, val):
		l = len(val)
		return '0' * (m - l) + val
	from bisect import bisect_right as br
	T = iin()
	for _ in range(T):
		(n, m) = lin()
		a = [int(input(), 2) for i in range(n)]
		a.sort()
		sa = set(a)
		mx = pow(2, m)
		ln = (mx - n) % 2
		md = (pow(2, m) - 1) // 2
		for i in range(-n, n + 1):
			if 0 <= md + i < mx:
				m1 = md + i
				lf = br(a, m1)
				rt = n - lf
				l1 = m1 - lf + 1
				r1 = mx - n - l1
				if l1 == r1 + 1 and ln == 1 or l1 == r1:
					md = m1
					break
		print(normalize(m, bin(md)[2:]))
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import sys
for _ in range(int(input())):
	(n, m) = map(int, sys.stdin.readline().split())
	mid = 2 ** m - 1 >> 1
	(nume, deno) = (2 ** m >> 1, 2 ** m)
	deleted = set()
	for num in (int(sys.stdin.readline().rstrip(), 2) for _ in range(n)):
		deleted.add(num)
		deno -= 1
		if num < mid:
			nume -= 1
		elif num == mid:
			while mid in deleted:
				mid += 1
	k = (deno + 1) // 2
	while k > nume:
		nume += 1
		mid += 1
		while mid in deleted:
			mid += 1
	while k < nume:
		nume -= 1
		mid -= 1
		while mid in deleted:
			mid -= 1
	print(bin(mid)[2:].zfill(m))


from sys import stdin, stdout
int_in = lambda : int(stdin.readline())
arr_in = lambda : [int(x) for x in stdin.readline().split()]
mat_in = lambda rows: [arr_in() for y in range(rows)]
str_in = lambda : stdin.readline().strip()
out = lambda o: stdout.write('{}\n'.format(o))
arr_out = lambda o: out(' '.join(map(str, o)))
bool_out = lambda o: out('YES' if o else 'NO')
tests = lambda : range(1, int_in() + 1)
case_out = lambda i, o: out('Case #{}: {}'.format(i, o))

def solve(n, m, strings):
	strings = set(strings)
	median = pow(2, m - 1)
	while median in strings:
		median += 1
	counts_lower = median
	for string in strings:
		if string < median:
			counts_lower -= 1
	needed_lower = (pow(2, m) - 1 - n) // 2
	while counts_lower != needed_lower:
		if counts_lower < needed_lower:
			median += 1
			if median not in strings:
				counts_lower += 1
		else:
			median -= 1
			if median not in strings:
				counts_lower -= 1
	return convert_to_binary_string_of_length(m, median)

def convert_to_binary_string_of_length(m, median):
	median = bin(median)[2:]
	median = '0' * m + median
	return median[len(median) - m:]
for i in tests():
	(n, m) = arr_in()
	strings = [int(str_in(), 2) for x in range(n)]
	out(solve(n, m, strings))


for i in range(int(input())):
	(n, m) = map(int, input().split())
	a = [int(input(), 2) for _ in range(n)]
	x = (2 ** m - n - 1) // 2
	for v in sorted(a):
		if v <= x:
			x += 1
	print('{0:0={1}b}'.format(x, m))


import sys
input = sys.stdin.readline

def stringminus(s):
	i = -1
	n = len(s)
	s2 = ['0'] * n
	for j in range(n):
		s2[j] = s[j]
	while s[i] == '0':
		s2[i] = '1'
		i -= 1
	s2[i] = '0'
	sol = s2[0]
	for i in range(1, n):
		sol += s2[i]
	return sol

def stringplus(s):
	i = -1
	n = len(s)
	s2 = ['0'] * n
	for j in range(n):
		s2[j] = s[j]
	while s[i] == '1':
		s2[i] = '0'
		i -= 1
	s2[i] = '1'
	sol = s2[0]
	for i in range(1, n):
		sol += s2[i]
	return sol
for f in range(int(input())):
	rem = set()
	med = '0'
	isc = 0
	(n, m) = map(int, input().split())
	for i in range(m - 1):
		med += '1'
	for i in range(n):
		s = input()
		s = s[0:m]
		if s > med:
			isc += 1
		if s < med:
			isc -= 1
		if s == med:
			if isc == 0:
				isc = -1
			else:
				isc = 2
		rem.add(s)
		if isc == -1:
			med = stringplus(med)
			while med in rem:
				med = stringplus(med)
			isc = 1
		if isc == 2:
			med = stringminus(med)
			while med in rem:
				med = stringminus(med)
			isc = 0
	print(med)


def solve():
	(n, m) = map(int, input().split())
	a = []
	for _ in range(n):
		a.append(input())
	a.sort()
	ans = int((2 ** m - n - 1) // 2)
	for i in a:
		if f(i) > ans:
			s = []
			for j in range(m):
				s.append(str(ans >> j & 1))
			print(''.join(s[::-1]))
			break
		else:
			ans += 1
	else:
		s = []
		for j in range(m):
			s.append(str(ans >> j & 1))
		print(''.join(s[::-1]))

def f(x):
	tmp = 0
	for (i, j) in enumerate(reversed(x)):
		tmp += 2 ** i * int(j)
	return tmp
t = int(input())
for _ in range(t):
	solve()


def read_int():
	return int(input())

def read_string_array():
	return input().split()

def read_int_array():
	return [int(_) for _ in read_string_array()]

def read_line():
	return input()

def solve(n, m, a):
	a = [int(_, 2) for _ in a]
	median = (2 ** m - 1) // 2
	k = 2 ** m
	removed = set()
	c = 0
	for b in a:
		removed.add(b)
		if b <= median:
			median += 1
			while median in removed:
				median += 1
		if k % 2 == 1:
			median -= 1
			while median in removed:
				median -= 1
		k -= 1
	return bin(median)[2:].zfill(m)
T = read_int()
for _ in range(T):
	(N, M) = read_int_array()
	A = [input() for _ in range(N)]
	print(solve(N, M, A))


from collections import Counter
import sys
sys.setrecursionlimit(10 ** 6)
mod = 1000000007
inf = int(1e+18)
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

def inverse(a):
	return pow(a, mod - 2, mod)

def usearch(x, a):
	lft = 0
	rgt = len(a) + 1
	while rgt - lft > 1:
		mid = (rgt + lft) // 2
		if a[mid] <= x:
			lft = mid
		else:
			rgt = mid
	return lft

def solve():
	(n, m) = map(int, input().split())
	a = 1 << m
	s = {int(input(), 2) for i in range(n)}
	mid = a // 2
	need = (a - n + 1) // 2
	cur = mid
	while True:
		lft = cur + 1
		for x in s:
			if x <= cur:
				lft -= 1
		if lft == need and cur not in s:
			print(bin(cur)[2:].zfill(m))
			return
		if lft < need:
			cur += 1
		else:
			cur -= 1

def main():
	n = int(input())
	for i in range(n):
		solve()
main()


T = int(input())
for _ in range(T):
	(n, m) = map(int, input().split())
	l = [int(input(), 2) for _ in range(n)]
	x = (2 ** m - 1 - n) // 2
	for i in sorted(l):
		if i <= x:
			x += 1
	ans = bin(x)[2:]
	if len(ans) < m:
		ans = '0' * (m - len(ans)) + ans
	print(ans)


from collections import Counter
T = int(input())
for _ in range(T):
	(n, m) = map(int, input().split())
	l = []
	for i in range(n):
		l.append(int(input(), 2))
	d = Counter(l)
	mid = (2 ** m - n - 1) // 2
	for i in sorted(l):
		if i <= mid:
			mid += 1
	print('{0:0={1}b}'.format(mid, m))


import sys
import math
import collections
import threading

def main():
	(n, m) = map(int, input().split())
	a = [int(input(), 2) for _ in range(n)]
	k = 2 ** m - len(a)
	med = (k - 1) // 2
	s = set()
	for num in a:
		s.add(num)
		if num <= med:
			med += 1
			while med in s:
				med += 1
	ans = '0' * m + bin(med)[2:]
	ans = ans[-m:]
	print(ans)
tn = int(input())
for _ in range(tn):
	main()


import sys

def bin_median(size: int, removed: 'Set[int]'):
	median = 2 ** (size - 1) - 1
	straddling = True
	skips_up = {}
	skips_down = {}
	for removed_x in removed:
		cutoff = median + 1 if straddling else median
		up = skips_up.get(removed_x, removed_x + 1)
		down = skips_down.get(removed_x, removed_x - 1)
		skips_down[up] = down
		skips_up[down] = up
		if removed_x >= cutoff:
			if not straddling:
				median = skips_down.get(median, median - 1)
		elif straddling:
			median = skips_up.get(median, median + 1)
		straddling = not straddling
	return median
count = int(sys.stdin.readline().rstrip())
for i in range(count):
	(t_count, size) = map(int, sys.stdin.readline().rstrip().split())
	removed = set((int(sys.stdin.readline().rstrip(), 2) for _ in range(t_count)))
	print(f'{{:0{size}b}}'.format(bin_median(size, removed)))


from sys import stdin
input = stdin.readline
for Ti in range(int(input().strip())):
	(n, m) = [int(x) for x in input().strip().split()]
	tc = 2 ** m
	mc = (tc - n + 1) // 2
	a = []
	for ni in range(n):
		a.append(int(input().strip(), 2))
	a.sort()
	a.append(tc)
	ne = a[0]
	ns = -1
	ci = 0
	while ci < len(a):
		cc = ne - ns - 1
		if mc - cc <= 0:
			ans = ns + mc
			break
		mc -= cc
		ci += 1
		ns = ne
		ne = a[ci]
	print(bin(ans)[2:].zfill(m))


import sys
input = sys.stdin.readline

def print(val):
	sys.stdout.write(val + '\n')

def prog():
	for _ in range(int(input())):
		(n, m) = map(int, input().split())
		missing = [int(input().strip(), 2) for i in range(n)]
		missing.sort()
		median = (2 ** m - n - 1) // 2
		for i in missing:
			if median >= i:
				median += 1
		output = bin(median)[2:]
		print('0' * (m - len(output)) + output)
prog()


import sys
input = sys.stdin.readline

def print(val):
	sys.stdout.write(val + '\n')

def prog():
	for _ in range(int(input())):
		(n, m) = map(int, input().split())
		missing = [int(input().strip(), 2) for i in range(n)]
		missing.sort()
		missing2 = set(missing)
		median = (2 ** m - n + 1) // 2
		curr = median - 1
		index = median
		while curr in missing2:
			curr -= 1
			index -= 1
		for i in missing:
			if curr > i:
				index -= 1
			else:
				break
		while index != median:
			curr += 1
			if curr not in missing:
				index += 1
		value = curr
		value = bin(value)[2:]
		value = '0' * (m - len(value)) + value
		print(value)
prog()


def ans(n, m, l, f, low, high):
	for i in range(low, high + 1):
		mi = 0
		ma = 0
		for j in l:
			if j <= i:
				mi += 1
			if j > i:
				ma += 1
		rig = f - i - ma
		lef = i + 1 - mi
		if lef - rig == 1 or rig == lef:
			return i
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	f = 2 ** m - 1
	l = []
	for i in range(n):
		l.append(int(input(), 2))
	med = 2 ** (m - 1) - 1
	if med - n < 0:
		low = 0
	else:
		low = med - n
	if med + n > f - 1:
		high = f
	else:
		high = med + n
	k = bin(ans(n, m, l, f, low, high))[2:]
	print('0' * (m - len(k)) + k)


def convert(z):
	s = ''
	while z > 0:
		if z % 2:
			s = '1' + s
		else:
			s = '0' + s
		z = z // 2
	return s

def num(s):
	sumi = 0
	for i in s:
		sumi = 2 * sumi + int(i)
	return sumi

def f(x):
	global lfi
	cnt1 = 0
	cnt2 = 0
	for i in lfi:
		if i == x:
			cnt1 = 1
		if i < x:
			cnt2 += 1
	return (cnt2, cnt1)

def bs(L, R, req):
	M = (L + R) // 2
	t = f(M)
	if M - t[0] == req and t[1] == 0:
		return M
	if M - t[0] <= req:
		return bs(M + 1, R, req)
	return bs(L, M - 1, req)
for _ in range(int(input())):
	l = input().split()
	n = int(l[0])
	m = int(l[1])
	lfi = []
	for i in range(n):
		s = input()
		no = num(s)
		lfi.append(no)
	req = (pow(2, m) - n - 1) // 2
	zo = bs(0, pow(2, m) - 1, req)
	z = convert(zo)
	for i in range(m - len(z)):
		print('0', end='')
	print(z)


import math

def solve():
	(n, m) = map(int, input().split())
	l = []
	for i in range(n):
		s = input()
		v = 0
		for i in s:
			v = v * 2 + ord(i) - ord('0')
		l.append(v)

	def findLessThan(x):
		cnt = 0
		for i in l:
			if i <= x:
				cnt += 1
		return x - cnt + 1
	low = 0
	best = 0
	high = (1 << m) - 1
	pos = ((1 << m) - n) // 2 + ((1 << m) - n) % 2
	while low <= high:
		mid = (low + high) // 2
		val = findLessThan(mid)
		if val >= pos:
			best = mid
			high = mid - 1
		else:
			low = mid + 1
	ans = ''
	for i in range(m):
		ans = chr(best % 2 + ord('0')) + ans
		best = best // 2
	print(ans)
	return
t = 1
t = int(input())
while t > 0:
	t -= 1
	solve()


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = [int(input(), 2) for i in range(n)]
	(L, R) = (0, 2 ** k - 1)
	r = R
	while L <= R:
		m = (L + R) // 2
		c = m + 1 - sum((x <= m for x in a))
		if c >= (2 ** k - n + 1) // 2:
			(r, R) = (m, m - 1)
		else:
			L = m + 1
	while r in a:
		r -= 1
	print(('{0:0%db}' % k).format(r))


def solve(mid):
	small = mid
	large = 2 ** m - mid - 1
	for val in s:
		if val < mid:
			small -= 1
		if val > mid:
			large -= 1
	return small < large

def solve2(mid):
	small = mid
	large = 2 ** m - mid - 1
	for val in s:
		if val < mid:
			small -= 1
		if val > mid:
			large -= 1
	return small <= large
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	s = set([int(input(), 2) for i in range(n)])
	ng = -1
	ok = 2 ** m + 2
	if len(s) % 2 == 0:
		while abs(ok - ng) > 1:
			mid = (ok + ng) // 2
			if mid in s:
				for i in range(ng + 1, ok):
					if i not in s:
						mid = i
						break
			if solve(mid):
				ng = mid
			else:
				ok = mid
		print('{:060b}'.format(ng)[::-1][0:m][::-1])
	else:
		while abs(ok - ng) > 1:
			mid = (ok + ng) // 2
			if mid in s:
				for i in range(ng + 1, ok):
					if i not in s:
						mid = i
						break
			if solve2(mid):
				ng = mid
			else:
				ok = mid
		print('{:060b}'.format(ng)[::-1][0:m][::-1])


def dec(b, m):
	return '{:0{}b}'.format(int(b, 2) - 1, m)

def inc(b, m):
	return '{:0{}b}'.format(int(b, 2) + 1, m)

def median(n, m, a):
	md = '0' + '1' * (m - 1)
	state = 1
	seen = {}
	for e in a:
		if e > md:
			state -= 1
			if state == -1:
				while True:
					md = dec(md, m)
					if md not in seen:
						break
				state = 1
		elif e < md:
			state += 1
			if state == 2:
				while True:
					md = inc(md, m)
					if md not in seen:
						break
				state = 0
		elif e == md:
			if state == 1:
				while True:
					md = inc(md, m)
					if md not in seen:
						break
				state = 0
			else:
				while True:
					md = dec(md, m)
					if md not in seen:
						break
				state = 1
		seen[e] = 1
	return md
t = int(input().strip())
for _ in range(t):
	(n, m) = list(map(int, input().strip().split()))
	a = []
	for _ in range(n):
		a.append(input().strip())
	print(median(n, m, a))


import sys
t = int(sys.stdin.readline().strip())
for _ in range(t):
	(n, m) = map(int, sys.stdin.readline().strip().split())
	s = set()
	mid = 2 ** (m - 1) - 1
	flag = 0
	for i in range(n):
		x = int(sys.stdin.readline().strip(), 2)
		s.add(x)
		if x > mid and flag == 0:
			flag = 1
		elif x > mid and flag == 1:
			flag = 0
			mid -= 1
			while mid in s:
				mid -= 1
		elif x < mid and flag == 0:
			flag = 1
			mid += 1
			while mid in s:
				mid += 1
		elif x < mid and flag == 1:
			flag = 0
		elif flag == 1:
			flag = 0
			mid -= 1
			while mid in s:
				mid -= 1
		else:
			flag = 1
			mid += 1
			while mid in s:
				mid += 1
	ans = bin(mid)[2:]
	ans = '0' * (m - len(ans)) + ans
	print(ans)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = [int(input(), 2) for _ in range(n)]
	a.sort()
	k = (1 << m) - n
	median = (k - 1) // 2
	for elem in a:
		if elem <= median:
			median += 1
	median = bin(median)[2:]
	median = (m - len(median)) * '0' + median
	print(median)


def read_int():
	return int(input())

def read_ints():
	return list(map(int, input().split(' ')))
t = read_int()
for case_num in range(t):
	(n, m) = read_ints()
	a = []
	for i in range(n):
		a.append(int(input(), 2))
	a.sort()
	k = 2 ** m - n
	ans = (k - 1) // 2
	for ai in a:
		if ai <= ans:
			ans += 1
	binary = '{:b}'.format(ans)
	print(binary.rjust(m, '0'))


from math import log
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	a = []
	for i in range(n):
		a.append(input())
	init = (2 ** m - 1) // 2
	seen = set()
	for i in a:
		bi = '0' * (m - len(bin(init)[2:])) + bin(init)[2:]
		if (2 ** m - len(seen)) % 2:
			if i >= bi:
				j = init - 1
				while '0' * (m - len(bin(j)[2:])) + bin(j)[2:] in seen:
					j -= 1
				init = j
		elif i <= bi:
			j = init + 1
			while '0' * (m - len(bin(j)[2:])) + bin(j)[2:] in seen:
				j += 1
			init = j
		seen.add(i)
	print('0' * (m - len(bin(init)[2:])) + bin(init)[2:])


t = int(input())
for _ in range(t):
	(m, n) = map(int, input().split())
	topn = (1 << n) - 1
	data = [int(input(), 2) for _ in range(m)]
	data.sort()
	data.reverse()
	median = topn // 2
	expected = (topn - m) // 2
	base = max(median - 200, 0)
	top = min(median + 200, topn)
	l = base
	for x in range(base, top + 1):
		l += 1
		while data and data[-1] <= x:
			data.pop()
			l -= 1
		if l - 1 == expected:
			num = bin(x)[2:]
			print('0' * (n - len(num)) + num)
			break


import sys
INF = 10 ** 20
MOD = 10 ** 9 + 7
I = lambda : list(map(int, input().split()))
from math import gcd
from math import ceil
from collections import defaultdict as dd, Counter
from bisect import bisect_left as bl, bisect_right as br

def solve():
	(n, m) = I()
	a = [0] * n
	for i in range(n):
		a[i] = int(input(), 2)
	a.sort()
	need = (2 ** m - n - 1) // 2
	(lo, hi) = (0, 2 ** m)
	while lo < hi:
		mid = (lo + hi) // 2
		k = bl(a, mid)
		if mid - 1 - k < need - 1:
			lo = mid + 1
		else:
			hi = mid
	while lo in a:
		lo += 1
	for i in range(m - 1, -1, -1):
		print(lo >> i & 1, end='')
	print()
(t,) = I()
while t:
	t -= 1
	solve()


t = int(input())
for kek in range(t):
	(n, m) = map(int, input().split())
	de = []
	for i in range(n):
		a = input()
		de.append(int(a, 2))
	mid = 2 ** (m - 1) - 1
	test = set(range(mid - 150, mid + 151))
	delta = 0
	for i in de:
		if i in test:
			test.remove(i)
		else:
			if i < mid - 150:
				delta -= 1
			if i > mid + 150:
				delta += 1
	test = list(test)
	test.sort()
	ans = test[(len(test) - delta) // 2]
	ans = bin(ans)[2:]
	print('0' * (m - len(ans)) + ans)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = []
	mp = {}
	for i in range(n):
		s = input()
		s = int(s, 2)
		a.append(s)
	l = 1 << m
	median = (l - 1) // 2
	for elem in a:
		l -= 1
		mp[elem] = 1
		if l % 2 == 1 and median >= elem:
			median += 1
			while mp.get(median, 0) == 1:
				median += 1
		elif l % 2 == 0 and median <= elem:
			median -= 1
			while mp.get(median, 0) == 1:
				median -= 1
	print(bin(median)[2:].zfill(m))


def check(x, nums, k):
	small = x + 1
	for i in nums:
		if i <= x:
			small -= 1
	if small <= (k - 1) // 2:
		return False
	return True

def solve(nums, m, ans):
	n = len(nums)
	low = 0
	high = pow(2, m) - 1
	x = 0
	k = pow(2, m) - n
	while low <= high:
		mid = (low + high) // 2
		if check(mid, nums, k):
			x = mid
			high = mid - 1
		else:
			low = mid + 1
	x = bin(x)[2:]
	if len(x) < m:
		x = '0' * (m - len(x)) + x
	ans.append(x)

def main():
	t = int(input())
	ans = []
	for i in range(t):
		(n, m) = map(int, input().split())
		nums = set()
		for j in range(n):
			x = int(input(), 2)
			nums.add(x)
		solve(nums, m, ans)
	for i in ans:
		print(i)
main()


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = (0 + 2 ** m - n - 1) // 2
	arr = []
	for i in range(n):
		arr.append(int(input(), 2))
	arr.sort()
	flag = True
	for i in arr:
		if i <= a:
			a += 1
	c = bin(a).replace('0b', '')
	for _ in range(m - len(c)):
		print('0', end='')
	print(c)


def main():
	for _ in range(int(input())):
		(n, m) = map(int, input().split())
		a = {int(input(), 2) for _ in range(n)}
		median = (2 ** m - n - 1) // 2
		new_a = a.copy()
		for _ in range(n):
			for ai in a:
				if ai <= median:
					median += 1
					new_a.discard(ai)
			a = new_a.copy()
		try:
			res = bin(median)[2:]
			print((m - len(res)) * '0' + res)
		except:
			print('0' * m)
main()


import sys
input = sys.stdin.buffer.readline
t = int(input())
for i in range(t):
	(a, b) = list(map(int, input().split()))
	x = 2 ** (b - 1)
	zz = min(100, 2 ** (b - 1))
	middle = [j for j in range(x - zz, x + zz)]
	left = 0
	right = 0
	for j in range(a):
		s = input()
		s = int(s, 2)
		if s in middle:
			middle.remove(s)
		elif s < min(middle):
			left += 1
		else:
			right += 1
	pos = (len(middle) - 1 + left - right) // 2
	ans = middle[pos]
	ans = '{0:b}'.format(ans)
	ans = '0' * (b - len(ans)) + ans
	print(ans)


import math
import random
import heapq, bisect
import sys
from collections import deque, defaultdict
from fractions import Fraction
import sys
import threading
from collections import defaultdict
mod = 10 ** 9 + 7
mod1 = 998244353
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class TreeNode:

	def __init__(self, k, v):
		self.key = k
		self.value = v
		self.left = None
		self.right = None
		self.parent = None
		self.height = 1
		self.num_left = 1
		self.num_total = 1

class AvlTree:

	def __init__(self):
		self._tree = None

	def add(self, k, v):
		if not self._tree:
			self._tree = TreeNode(k, v)
			return
		node = self._add(k, v)
		if node:
			self._rebalance(node)

	def _add(self, k, v):
		node = self._tree
		while node:
			if k < node.key:
				if node.left:
					node = node.left
				else:
					node.left = TreeNode(k, v)
					node.left.parent = node
					return node.left
			elif node.key < k:
				if node.right:
					node = node.right
				else:
					node.right = TreeNode(k, v)
					node.right.parent = node
					return node.right
			else:
				node.value = v
				return

	@staticmethod
	def get_height(x):
		return x.height if x else 0

	@staticmethod
	def get_num_total(x):
		return x.num_total if x else 0

	def _rebalance(self, node):
		n = node
		while n:
			lh = self.get_height(n.left)
			rh = self.get_height(n.right)
			n.height = max(lh, rh) + 1
			balance_factor = lh - rh
			n.num_total = 1 + self.get_num_total(n.left) + self.get_num_total(n.right)
			n.num_left = 1 + self.get_num_total(n.left)
			if balance_factor > 1:
				if self.get_height(n.left.left) < self.get_height(n.left.right):
					self._rotate_left(n.left)
				self._rotate_right(n)
			elif balance_factor < -1:
				if self.get_height(n.right.right) < self.get_height(n.right.left):
					self._rotate_right(n.right)
				self._rotate_left(n)
			else:
				n = n.parent

	def _remove_one(self, node):
		replacement = node.left or node.right
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = replacement
			else:
				node.parent.right = replacement
			replacement.parent = node.parent
			node.parent = None
		else:
			self._tree = replacement
			replacement.parent = None
		node.left = None
		node.right = None
		node.parent = None
		self._rebalance(replacement)

	def _remove_leaf(self, node):
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = None
			else:
				node.parent.right = None
			self._rebalance(node.parent)
		else:
			self._tree = None
		node.parent = None
		node.left = None
		node.right = None

	def remove(self, k):
		node = self._get_node(k)
		if not node:
			return
		if AvlTree._is_leaf(node):
			self._remove_leaf(node)
			return
		if node.left and node.right:
			nxt = AvlTree._get_next(node)
			node.key = nxt.key
			node.value = nxt.value
			if self._is_leaf(nxt):
				self._remove_leaf(nxt)
			else:
				self._remove_one(nxt)
			self._rebalance(node)
		else:
			self._remove_one(node)

	def get(self, k):
		node = self._get_node(k)
		return node.value if node else -1

	def _get_node(self, k):
		if not self._tree:
			return None
		node = self._tree
		while node:
			if k < node.key:
				node = node.left
			elif node.key < k:
				node = node.right
			else:
				return node
		return None

	def get_at(self, pos):
		x = pos + 1
		node = self._tree
		while node:
			if x < node.num_left:
				node = node.left
			elif node.num_left < x:
				x -= node.num_left
				node = node.right
			else:
				return (node.key, node.value)
		raise IndexError('Out of ranges')

	@staticmethod
	def _is_left(node):
		return node.parent.left and node.parent.left == node

	@staticmethod
	def _is_leaf(node):
		return node.left is None and node.right is None

	def _rotate_right(self, node):
		if not node.parent:
			self._tree = node.left
			node.left.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.left
			node.left.parent = node.parent
		else:
			node.parent.right = node.left
			node.left.parent = node.parent
		bk = node.left.right
		node.left.right = node
		node.parent = node.left
		node.left = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	def _rotate_left(self, node):
		if not node.parent:
			self._tree = node.right
			node.right.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.right
			node.right.parent = node.parent
		else:
			node.parent.right = node.right
			node.right.parent = node.parent
		bk = node.right.left
		node.right.left = node
		node.parent = node.right
		node.right = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	@staticmethod
	def _get_next(node):
		if not node.right:
			return node.parent
		n = node.right
		while n.left:
			n = n.left
		return n

class SegmentTree1:

	def __init__(self, data, default=300006, func=lambda a, b: min(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree:

	def __init__(self, data, default=0, func=lambda a, b: a + b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD

def powm(a, n, m):
	if a == 1 or n == 0:
		return 1
	if n % 2 == 0:
		s = powm(a, n // 2, m)
		return s * s % m
	else:
		return a * powm(a, n - 1, m) % m

def sort_list(list1, list2):
	zipped_pairs = zip(list2, list1)
	z = [x for (_, x) in sorted(zipped_pairs)]
	return z

def product(l):
	por = 1
	for i in range(len(l)):
		por *= l[i]
	return por

def binarySearchCount(arr, n, key):
	left = 0
	right = n - 1
	count = 0
	while left <= right:
		mid = int((right + left) / 2)
		if arr[mid] <= key:
			count = mid + 1
			left = mid + 1
		else:
			right = mid - 1
	return count

def countdig(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def binary(x, length):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y

def countGreater(arr, n, k):
	l = 0
	r = n - 1
	leftGreater = n
	while l <= r:
		m = int(l + (r - l) / 2)
		if arr[m] > k:
			leftGreater = m
			r = m - 1
		else:
			l = m + 1
	return n - leftGreater

class TrieNode:

	def __init__(self):
		self.children = [None] * 26
		self.isEndOfWord = False

class Trie:

	def __init__(self):
		self.root = self.getNode()

	def getNode(self):
		return TrieNode()

	def _charToIndex(self, ch):
		return ord(ch) - ord('a')

	def insert(self, key):
		pCrawl = self.root
		length = len(key)
		for level in range(length):
			index = self._charToIndex(key[level])
			if not pCrawl.children[index]:
				pCrawl.children[index] = self.getNode()
			pCrawl = pCrawl.children[index]
		pCrawl.isEndOfWord = True

	def search(self, key):
		pCrawl = self.root
		length = len(key)
		for level in range(length):
			index = self._charToIndex(key[level])
			if not pCrawl.children[index]:
				return False
			pCrawl = pCrawl.children[index]
		return pCrawl != None and pCrawl.isEndOfWord

class Node:

	def __init__(self, data):
		self.data = data
		self.count = 0
		self.left = None
		self.right = None

class BinaryTrie:

	def __init__(self):
		self.root = Node(0)

	def insert(self, pre_xor):
		self.temp = self.root
		for i in range(31, -1, -1):
			val = pre_xor & 1 << i
			if val:
				if not self.temp.right:
					self.temp.right = Node(0)
				self.temp = self.temp.right
				self.temp.count += 1
			if not val:
				if not self.temp.left:
					self.temp.left = Node(0)
				self.temp = self.temp.left
				self.temp.count += 1
		self.temp.data = pre_xor

	def query(self, xor):
		self.temp = self.root
		for i in range(31, -1, -1):
			val = xor & 1 << i
			if not val:
				if self.temp.left and self.temp.left.count > 0:
					self.temp = self.temp.left
				elif self.temp.right:
					self.temp = self.temp.right
			elif self.temp.right and self.temp.right.count > 0:
				self.temp = self.temp.right
			elif self.temp.left:
				self.temp = self.temp.left
			self.temp.count -= 1
		return xor ^ self.temp.data
for ik in range(int(input())):
	(m, n) = map(int, input().split())
	ans = 2 ** (n - 1) - 1
	t = n
	n = 2 ** n
	pre = ans
	nex = ans + 1
	prev = defaultdict(int)
	next = defaultdict(int)
	s = set()
	for i in range(m):
		w = int(input(), 2)
		s.add(w)
		next[w - 1] += next[w]
		prev[w + 1] -= prev[w]
		if w < ans:
			if pre == nex:
				pre -= 1
			else:
				while ans + next[ans] + 1 in s:
					ans += next[ans] + 1
				ans += next[ans] + 1
				nex -= 1
		elif w > ans:
			if pre < nex:
				nex -= 1
			else:
				while ans - prev[ans] - 1 in s:
					ans -= prev[ans] + 1
				ans -= prev[ans] + 1
				pre -= 1
		elif pre == nex:
			while ans - prev[ans] - 1 in s:
				ans -= prev[ans] + 1
			ans -= prev[ans] + 1
			pre -= 1
		else:
			while ans + next[ans] + 1 in s:
				ans += next[ans] + 1
			ans += next[ans] + 1
			nex -= 1
	w = bin(ans)[2:]
	w = '0' * (t - len(w)) + w
	print(w)


for i in range(int(input())):
	(n, m) = list(map(int, input().split()))
	a = sorted([int(input(), base=2) for i in range(n)])
	k = (2 ** m - n - 1) // 2
	i = 0
	while i < n and a[i] <= k:
		i += 1
		k += 1
	print('0' * (m - len(bin(k)[2:])) + bin(k)[2:])


import io
import os
from collections import Counter, defaultdict, deque
from bisect import bisect, bisect_left, bisect_right

def bisect_f(f, lo, hi):
	while hi - lo > 1:
		mid = (lo + hi) // 2
		if f(mid):
			lo = mid
		else:
			hi = mid
	return lo

def solve(N, M, A):
	A = [int(x, 2) for x in A]
	A.sort()
	K = 2 ** M - N
	target = (K - 1) // 2

	def getRank(i):
		return i - bisect_right(A, i)
	lo = -1
	hi = 2 ** M + 1
	assert getRank(lo) < target <= getRank(hi)
	index = bisect_f(lambda i: getRank(i) < target, lo, hi)
	assert getRank(index) < target <= getRank(index + 1)
	return bin(index + 1)[2:].rjust(M, '0')
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
T = int(input())
for t in range(T):
	(N, M) = [int(x) for x in input().split()]
	A = [input().decode().rstrip() for i in range(N)]
	ans = solve(N, M, A)
	print(ans)


from collections import defaultdict as dd
from collections import deque
import bisect
import heapq

def ri():
	return int(input())

def rl():
	return list(map(int, input().split()))

def solve():
	(n, m) = rl()
	A = set()
	for i in range(n):
		A.add(int(input(), 2))
	if m == 1:
		if 0 in A:
			print(1)
			return
		else:
			print(0)
			return
	mid = pow(2, m - 1)
	below = mid
	above = below - 1
	for a in A:
		if a < mid:
			below -= 1
		elif a > mid:
			above -= 1
	while below > above:
		mid -= 1
		if mid not in A:
			below -= 1
		if mid + 1 not in A:
			above += 1
	while below < above - 1:
		mid += 1
		if mid not in A:
			above -= 1
		if mid - 1 not in A:
			below += 1
	while mid in A:
		if below == above:
			mid -= 1
		else:
			mid += 1
	s = bin(mid)[2:]
	if len(s) < m:
		s = '0' * (m - len(s)) + s
	print(s)
mode = 'T'
if mode == 'T':
	t = ri()
	for i in range(t):
		solve()
else:
	solve()


from sys import stdin, stdout

def solve():
	(n, m) = map(int, stdin.readline().split())
	median = (1 << m - 1) - 1
	(left, right) = (median, (1 << m) - 1 - median)
	deleted = []
	for _ in range(n):
		x = int(input(), 2)
		if left == right:
			left -= 1
			if x >= median:
				median -= 1
				while median in deleted:
					median -= 1
		else:
			right -= 1
			if x <= median:
				median += 1
				while median in deleted:
					median += 1
		deleted.append(x)
	median = bin(median)[2:]
	stdout.write('0' * (m - len(median)) + median + '\n')
for _ in range(int(stdin.readline())):
	solve()


import sys, math, itertools
from collections import Counter, deque, defaultdict
from bisect import bisect_left, bisect_right
from heapq import heappop, heappush, heapify, nlargest
from copy import deepcopy
mod = 10 ** 9 + 7
INF = float('inf')

def inp():
	return int(sys.stdin.readline())

def inpl():
	return list(map(int, sys.stdin.readline().split()))

def inpl_1():
	return list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))
for _ in range(inp()):
	(n, m) = inpl()
	a = []
	for _ in range(n):
		tmp = list(sys.stdin.readline())
		tmp = tmp[:m]
		a.append(int(''.join(tmp), 2))
	sa = set(a)
	k = (2 ** m - n - 1) // 2
	cnt = sum((x <= k for x in a))
	for i in range(cnt):
		k += 1
		while k in sa:
			k += 1
	tmp = list(bin(k))
	tmp = tmp[2:]
	res = []
	for i in range(m - len(tmp)):
		res.append('0')
	for x in tmp:
		res.append(x)
	print(''.join(res))


import math
import sys
t = int(input())
while t > 0:
	(n, m) = [int(i) for i in input().split(' ')]
	a = [int(input(), 2) for i in range(n)]
	ne = ((1 << m) - n - 1) // 2 + 1
	me = (1 << m - 1) - 1
	while True:
		l = me + 1
		fl = 0
		for i in a:
			fl = fl or i == me
			if i <= me:
				l -= 1
		if l == ne and fl == 0:
			s = bin(me)[2:]
			while len(s) < m:
				s = '0' + s
			print(s)
			break
		elif l < ne:
			me += 1
		else:
			me -= 1
	t -= 1


T = int(input())
for t in range(T):
	(n, m) = map(int, input().split())
	nums = set()
	even = True
	curr_med = (2 ** m - 1) // 2
	for i in range(n):
		num = int(input(), 2)
		nums.add(num)
		if num > curr_med:
			if not even:
				curr_med -= 1
				while curr_med in nums:
					curr_med -= 1
		elif num < curr_med:
			if even:
				curr_med += 1
				while curr_med in nums:
					curr_med += 1
		elif even:
			curr_med += 1
			while curr_med in nums:
				curr_med += 1
		else:
			curr_med -= 1
			while curr_med in nums:
				curr_med -= 1
		if even:
			even = False
		else:
			even = True
	binary_string = '{0:b}'.format(curr_med)
	print((m - len(binary_string)) * '0' + binary_string)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	x = (2 ** m - n - 1) // 2
	arr = []
	for i in range(n):
		arr.append(int(input(), 2))
	arr.sort()
	for i in range(0, n):
		if arr[i] <= x:
			x += 1
	if x in arr:
		x += 1
	y = bin(x)[2:]
	print('0' * (m - len(y)) + y)


from __future__ import division, print_function
import itertools
import sys
import os
from io import BytesIO, IOBase
if sys.version_info[0] < 3:
	input = raw_input
	range = xrange
	filter = itertools.ifilter
	map = itertools.imap
	zip = itertools.izip

def is_it_local():
	script_dir = str(os.getcwd()).split('/')
	username = 'dipta007'
	return username in script_dir

def READ(fileName):
	if is_it_local():
		sys.stdin = open(f'./{fileName}', 'r')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
if not is_it_local():
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
	input = lambda : sys.stdin.readline().rstrip('\r\n')

def input1(type=int):
	return type(input())

def input2(type=int):
	[a, b] = list(map(type, input().split()))
	return (a, b)

def input3(type=int):
	[a, b, c] = list(map(type, input().split()))
	return (a, b, c)

def input_array(type=int):
	return list(map(type, input().split()))

def input_string():
	s = input()
	return list(s)
import math
removed = []

def check(mid):
	org = mid
	for v in removed:
		if v <= mid:
			org -= 1
	return org

def s_to_b(st):
	c = 1
	res = 0
	for i in range(len(st) - 1, -1, -1):
		if st[i] == '1':
			res += c
		c *= 2
	return res

def b_to_s(n):
	res = ''
	while n:
		nw = n % 2
		if nw:
			res += '1'
		else:
			res += '0'
		n = n // 2
	li = list(res)
	li.reverse()
	return ''.join(li)
	return res

def main():
	t = input1()
	for ci in range(t):
		global removed
		removed = []
		(n, m) = input2()
		for i in range(n):
			st = input_string()
			removed.append(s_to_b(st))
		removed.sort()
		low = 0
		high = (1 << m) - 1
		need = ((1 << m) - n - 1) // 2
		res = -1
		while low <= high:
			mid = (low + high) // 2
			while mid in removed and mid > low:
				mid -= 1
			while mid in removed and mid < high:
				mid += 1
			pos = check(mid)
			if pos < need:
				low = mid + 1
			else:
				high = mid - 1
				res = mid
		res = b_to_s(res)
		res = '0' * (m - len(res)) + res
		print(res)
	pass
READ('in.txt')
main()


import sys
input = sys.stdin.readline
t = int(input())
import math
for t1 in range(t):
	(k, n) = list(map(int, input().split(' ')))
	l = []
	for i in range(k):
		s = input()
		s = s.strip()
		l.append(int(s, 2))
	l.sort()
	a = 0
	curr = '0' + '1' * (n - 1)
	curr = int(curr, 2)
	temp = 1 << n
	d = {}
	for i in range(k):
		d[l[i]] = 1
		if temp % 2 == 0:
			if l[i] > curr:
				a = 1
			else:
				while d.get(curr + 1, 0) == 1:
					curr += 1
				curr += 1
		elif l[i] >= curr:
			while d.get(curr - 1, 0) == 1:
				curr -= 1
			curr -= 1
		else:
			a = 1
		temp -= 1
	z = bin(curr)[2:]
	if len(z) < n:
		diff = n - len(z)
		z = '0' * diff + z
	print(z)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	kl = []
	for i in range(n):
		kl.append(int(input(), 2))
	kl.sort()
	k = (2 ** m - 1 - n) // 2
	for i in kl:
		if k >= i:
			k += 1
	k = bin(k).replace('0b', '')
	k = (m - len(k)) * '0' + k
	print(k)


import bisect
TT = int(input())
for loop in range(TT):
	(n, m) = map(int, input().split())
	rem = []
	rd = {}
	for i in range(n):
		x = input()
		rem.append(int(x, 2))
		rd[int(x, 2)] = 1
	rem.sort()
	l = -1
	r = 2 ** m - 1
	k = 2 ** m - n
	d = (k - 1) // 2
	while r - l != 1:
		mid = (l + r) // 2
		mininum = bisect.bisect_left(rem, mid)
		if mid - mininum >= d:
			r = mid
		else:
			l = mid
	while r in rd:
		r += 1
	print(format(r, 'b').zfill(m))


import sys
input = sys.stdin.readline

def moveleft(s):
	n = int('0b' + s, 2)
	n -= 1
	ss = format(n, '#b')[2:]
	return '0' * (len(s) - len(ss)) + ss

def moveright(s):
	n = int('0b' + s, 2)
	n += 1
	ss = format(n, '#b')[2:]
	return '0' * (len(s) - len(ss)) + ss

def solve(n, L, check):
	mid = '0' + '1' * (n - 1)
	even = True
	for i in L:
		check[i] = True
		if i > mid:
			if even:
				even = False
			else:
				mid = moveleft(mid)
				while mid in check:
					mid = moveleft(mid)
				even = True
		elif i == mid:
			if even:
				mid = moveright(mid)
				while mid in check:
					mid = moveright(mid)
				even = False
			else:
				mid = moveleft(mid)
				while mid in check:
					mid = moveleft(mid)
				even = True
		elif even:
			mid = moveright(mid)
			while mid in check:
				mid = moveright(mid)
			even = False
		else:
			even = True
	return mid
for i in ' ' * int(input()):
	(n, m) = map(int, input().split())
	L = []
	check = dict()
	for j in ' ' * n:
		L.append(input().strip())
	print(solve(m, L, check))


import sys
input = sys.stdin.readline
from bisect import bisect_left

def solve(n, m, A):
	k = pow(2, m) - n
	border = (k + 1) // 2
	ok = 0
	ng = 1 << 60
	while ng - ok > 1:
		mid = (ok + ng) // 2
		cnt = bisect_left(A, mid)
		num = mid + 1 - cnt
		if num <= border:
			ok = mid
		else:
			ng = mid
	if ok in A:
		return ok - 1
	return ok

def main():
	t = int(input())
	for _ in range(t):
		(n, m) = map(int, input().split())
		A = [int(input(), 2) for _ in range(n)]
		A.sort()
		ans = solve(n, m, A)
		ans = bin(ans)[2:].zfill(m)
		sys.stdout.write(ans + '\n')
main()


import sys
max_int = 1000000001
min_int = -max_int
t = int(input())
for _t in range(t):
	(n, m) = map(int, sys.stdin.readline().split())
	to_skip = []
	for _n in range(n):
		s = int(sys.stdin.readline()[:-1], base=2)
		to_skip.append(s)
	to_skip.sort()
	mid = (2 ** m - n - 1) // 2
	for elem in to_skip:
		if elem <= mid:
			mid += 1
		else:
			break
	print(('{0:0>' + str(m) + 'b}').format(mid))


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	cnt = int(pow(2, m))
	a = [0] * n
	for i in range(n):
		a[i] = int(input(), 2)
	low = max(cnt // 2 - 105, 0)
	high = min(cnt // 2 + 105, cnt - 1)
	ans = 0
	while low <= high:
		mid = (low + high) // 2
		less = mid - sum((x < mid for x in a))
		more = cnt - mid - 1 - sum((x > mid for x in a))
		equal = sum((x == mid for x in a))
		if equal == 0 and (less == more or less == more - 1):
			ans = mid
			break
		if equal == 0:
			if less < more:
				low = mid + 1
			else:
				high = mid - 1
		elif equal == 1:
			if more > less:
				low = mid + 1
			else:
				high = mid - 1
	fv = bin(ans).replace('0b', '')
	for i in range(m - len(fv)):
		print('0', end='')
	print(fv)


from bisect import bisect
from sys import stdin
input = iter(stdin.readlines()).__next__

def is_median(a, m, n, median):
	idx = bisect(a, median)
	left = median - idx
	right = 2 ** m - 1 - median - (n - idx)
	if n % 2 == 0 and left == right - 1:
		return True
	elif n % 2 == 1 and left == right:
		return True
	return False
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	a = sorted([int(input(), base=2) for _ in range(n)])
	aset = set(a)
	median = 2 ** (m - 1)
	for med in range(median - n, median + n + 1):
		if is_median(a, m, n, med):
			ans = bin(med)[2:]
			print('0' * (m - len(ans)) + ans)
			break


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

def RLL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
	return int(input())

def print_list(l):
	print(' '.join(map(str, l)))
for _ in range(N()):
	(n, m) = RL()
	s = set()
	key = (1 << m) - 1 >> 1
	(small, big) = (0, 0)
	MAX = 1 << m
	for _ in range(n):
		tmp = int(input(), base=2)
		if tmp <= key:
			small += 1
		else:
			big += 1
		s.add(tmp)
	if big >= small:
		k = big - small >> 1
		key += 1
		for _ in range(k + 1):
			for mid in range(key - 1, -1, -1):
				if mid not in s:
					key = mid
					break
	else:
		k = small - big + 1 >> 1
		for _ in range(k):
			for mid in range(key + 1, MAX + 3):
				if mid not in s:
					key = mid
					break
	s = str(bin(key))[2:]
	s = '0' * (m - len(s)) + s
	print(s)


import queue
import math
t = int(input())

def add(x, r):
	while True:
		x += 1
		if x not in r:
			return x

def sub(x, r):
	while True:
		x -= 1
		if x not in r:
			return x
while t:
	line = input().split()
	(n, M) = (int(line[0]), int(line[1]))
	cnt = m = 1 << M
	m = (m - 1) // 2
	r = set()
	for i in range(n):
		x = int(input(), 2)
		r.add(x)
		if x == m:
			m = add(x, r) if cnt % 2 == 0 else sub(x, r)
		elif x < m:
			if cnt % 2 == 0:
				m = add(m, r)
		elif cnt % 2 == 1:
			m = sub(m, r)
		cnt -= 1
	s = str(bin(m))[2:]
	while len(s) < M:
		s = '0' + s
	print(s)
	t -= 1


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	l = []
	for j in range(n):
		s = input()
		l.append(int(s, 2))
	l = sorted(l)
	length = 2 ** m
	newlen = length - n
	med = newlen // 2
	if newlen % 2 == 0:
		med = med - 1
	ele = med
	for j in range(len(l)):
		if l[j] <= med:
			med = med + 1
	med = bin(med)
	med = med[2:]
	count = m - len(med)
	while count > 0:
		print(0, end='')
		count = count - 1
	for j in range(len(med)):
		print(med[j], end='')
	print()


from sys import stdin
for case in range(int(stdin.readline())):
	(n, m) = [int(x) for x in stdin.readline().split()]
	mid = 2 ** (m - 1) - 1
	half = True
	used = []
	for a in range(n):
		used.append(int(stdin.readline(), 2))
	used.sort()
	passed = set()
	for a in used:
		passed.add(a)
		if a == mid:
			if half:
				half = False
				mid += 1
				while mid in passed:
					mid += 1
			else:
				half = True
				mid -= 1
				while mid in passed:
					mid -= 1
		elif a < mid:
			if half:
				mid += 1
				while mid in passed:
					mid += 1
				half = False
			else:
				half = True
		elif half:
			half = False
		else:
			half = True
			mid -= 1
			while mid in passed:
				mid -= 1
	bruh = '{0:b}'.format(mid)
	print('0' * (m - len(bruh)) + bruh)


def op_one_median(median, removed, op):
	median += op
	while median in removed:
		median += op
	return median

def add_one_median(median, removed):
	res = op_one_median(median, removed, 1)
	return res

def remove_one_median(median, removed):
	res = op_one_median(median, removed, -1)
	return res
T = int(input())
for t in range(T):
	(N, M) = list(map(int, input().split()))
	median = 2 ** (M - 1) - 1
	removed = set()
	move_median_up = True
	for i in range(N):
		r = int(input(), 2)
		removed.add(r)
		if r < median:
			if move_median_up:
				median = add_one_median(median, removed)
		elif r > median:
			if not move_median_up:
				median = remove_one_median(median, removed)
		else:
			f = add_one_median if move_median_up else remove_one_median
			median = f(median, removed)
		move_median_up = not move_median_up
	print(format(median, '0{}b'.format(M)))


for nt in range(int(input())):
	(n, m) = map(int, input().split())
	r = []
	for i in range(n):
		r.append(int(input(), 2))
	r.sort()
	left = 2 ** m - n
	med = (left - 1) // 2
	for i in range(n):
		if r[i] <= med:
			med += 1
	ans = bin(med)[2:]
	ans = '0' * (m - len(ans)) + ans
	print(ans)


def solve():
	ans = 2 ** (m - 1) - 1
	l = 0
	removed = set()
	for i in range(n):
		removed.add(a[i])
		if l == 0:
			if a[i] <= ans:
				ans = ansplus(ans, removed)
		elif a[i] >= ans:
			ans = ansminus(ans, removed)
		l ^= 1
	ans = format(ans, '0' + str(m) + 'b')
	print(ans)
	return

def ansplus(ans, removed):
	ans += 1
	while ans in removed:
		ans += 1
	return ans

def ansminus(ans, removed):
	ans -= 1
	while ans in removed:
		ans -= 1
	return ans
t = int(input())
for tt in range(1, t + 1):
	(n, m) = [int(i) for i in input().split(' ')]
	a = []
	for i in range(n):
		a.append(int(input(), 2))
	solve()


import sys
readline = sys.stdin.buffer.readline
read = sys.stdin.read
ns = lambda : readline().rstrip()
ni = lambda : int(readline().rstrip())
nm = lambda : map(int, readline().split())
nl = lambda : list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

def solve():
	(n, m) = nm()
	l = [int(ns(), 2) for t in [0] * n]
	s = set(l)
	k = ((1 << m) - n - 1) // 2
	(ng, ok) = (1 << m, 0)
	while ng - ok > 1:
		mid = (ng + ok) // 2
		c = mid - sum((x <= mid for x in l))
		if c <= k:
			ok = mid
		else:
			ng = mid
	for i in range(ok - 110, ok + 110):
		if i not in s and i - sum((x < i for x in l)) == k:
			print(bin(i + (1 << 65))[-m:])
			return
	return
T = ni()
for _ in range(T):
	solve()


import sys
buff_readline = sys.stdin.readline
readline = sys.stdin.readline
INF = 2 ** 62 - 1

def read_int():
	return int(buff_readline())

def read_int_n():
	return list(map(int, buff_readline().split()))

def read_str():
	return readline().strip()

class Bisect:

	def __init__(self, func):
		self.__func = func

	def bisect_left(self, x, lo, hi):
		while lo < hi:
			mid = (lo + hi) // 2
			if self.__func(mid) < x:
				lo = mid + 1
			else:
				hi = mid
		return lo

	def bisect_right(self, x, lo, hi):
		while lo < hi:
			mid = (lo + hi) // 2
			if x < self.__func(mid):
				hi = mid
			else:
				lo = mid + 1
		return lo
from bisect import bisect_left

def slv(N, M, A):
	A = [int(a, base=2) for a in A]
	A.sort()

	def f(x):
		i = bisect_left(A, x)
		if i < len(A) and A[i] == x:
			i += 1
		return x - i
	ans = bin(Bisect(lambda x: f(x)).bisect_right((2 ** M - N - 1) // 2 - 1, 0, 2 ** M))
	ans = ans[2:]
	if len(ans) < M:
		ans = '0' * (M - len(ans)) + ans
	return ans

def main():
	T = read_int()
	for _ in range(T):
		(N, M) = read_int_n()
		A = [read_str() for _ in range(N)]
		print(slv(N, M, A))
main()


import sys, re, math
from collections import deque, defaultdict, Counter, OrderedDict
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from heapq import heappush, heappop, heapify, nlargest, nsmallest

def STR():
	return list(input())

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST():
	return list(map(int, input().split()))

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def sortListWithIndex(listOfTuples, idx):
	return sorted(listOfTuples, key=lambda x: x[idx])

def sortDictWithVal(passedDic):
	temp = sorted(passedDic.items(), key=lambda kv: (kv[1], kv[0]))[::-1]
	toret = {}
	for tup in temp:
		toret[tup[0]] = tup[1]
	return toret

def sortDictWithKey(passedDic):
	return dict(OrderedDict(sorted(passedDic.items())))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def calcNext(num):
	for i in range(num + 1, 2 ** m):
		if i not in vis:
			return i
	return -1

def calcPrev(num):
	for i in range(num - 1, -1, -1):
		if i not in vis:
			return i
	return -1
t = INT()
while t != 0:
	(n, m) = MAP()
	currLen = 2 ** m
	currMed = (2 ** m - 1) // 2
	vis = set()
	for _ in range(n):
		torem = int(input(), 2)
		if currLen % 2 == 0:
			currLen -= 1
			vis.add(torem)
			if torem <= currMed:
				currMed = calcNext(currMed)
		else:
			currLen -= 1
			vis.add(torem)
			if torem >= currMed:
				currMed = calcPrev(currMed)
	print(format(currMed, '0' + str(m) + 'b'))
	t -= 1


from collections import defaultdict as dd
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	med = (1 << m - 1) - 1
	num = dd(int)
	for i in range(n):
		d = int(input(), 2)
		num[d] = 1
		if i % 2:
			x = med - 1
			if d >= med:
				while num[x]:
					x -= 1
				med = x
		else:
			x = med + 1
			if d <= med:
				while num[x]:
					x += 1
				med = x
	print(bin(med)[2:].zfill(m))


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
t = int(input())
from collections import defaultdict
for i in range(t):
	(n, m) = map(int, input().split())
	l = []
	d = defaultdict(int)
	for j in range(n):
		l.append(int(input(), 2))
	x = pow(2, m - 1) - 1
	ln = 0
	for j in l:
		if ln % 2 != 0:
			if j >= x:
				x -= 1
				while d[x] == 1:
					x -= 1
				d[j] = 1
			else:
				d[j] = 1
		elif j <= x:
			x += 1
			while d[x] == 1:
				x += 1
			d[j] = 1
		else:
			d[j] = 1
		ln = ln ^ 1
	ans = bin(x).lstrip('0b')
	ans = '0' * (m - len(ans)) + ans
	print(ans)


import sys
inp = [x for x in sys.stdin.read().split()]
ii = 0
ttt = int(inp[ii])
ii += 1
res = []
for _ in range(ttt):
	(n, m) = (int(inp[ii]), int(inp[ii + 1]))
	ii += 2
	a = []
	for _ in range(n):
		temp = inp[ii]
		ii += 1
		x = 0
		for i in range(m):
			if temp[i] == '1':
				x += 1 << m - 1 - i
		a.append(x)
	t = ((1 << m) - n - 1) // 2
	(low, high) = (0, 1 << m)
	while high - low > 1:
		mid = low + high >> 1
		if mid - sum([x < mid for x in a]) <= t:
			low = mid
		else:
			high = mid
	res.append(''.join((str(int(not not low & 1 << i)) for i in range(m - 1, -1, -1))))
print('\n'.join((str(x) for x in res)))


def add(middle):
	middle = list(middle)
	for i in range(len(middle) - 1, -1, -1):
		if middle[i] == '0':
			middle[i] = '1'
			break
		middle[i] = '0'
	s = ''
	for i in middle:
		s += i
	return s

def subtract(middle):
	middle = list(middle)
	for i in range(len(middle) - 1, -1, -1):
		if middle[i] == '1':
			middle[i] = '0'
			break
		middle[i] = '1'
	s = ''
	for i in middle:
		s += i
	return s
t = int(input())
while t:
	t += -1
	(n, m) = map(int, input().split())
	l = []
	middle = '0' + '1' * (m - 1)
	mp = {}
	for i in range(max(0, 2 ** (m - 1) - 100), min(2 ** m, 2 ** (m - 1) + 101)):
		tmp = bin(i)[2:]
		tmp = '0' * (m - len(tmp)) + tmp
		mp[tmp] = 1
	(c1, c2) = (0, 0)
	for i in range(n):
		s = input()
		if s <= middle:
			c1 -= -1
			if s == middle:
				if c1 % 2 == 0:
					middle = subtract(middle)
					while mp[middle] == 0:
						middle = subtract(middle)
				else:
					middle = add(middle)
					while mp[middle] == 0:
						middle = add(middle)
			elif c1 % 2:
				middle = add(middle)
				while mp[middle] == 0:
					middle = add(middle)
		else:
			c1 -= -1
			if c1 % 2 == 0:
				middle = subtract(middle)
				while mp[middle] == 0:
					middle = subtract(middle)
		mp[s] = 0
	print(middle)


cin = lambda : int(input())
mi = lambda : map(int, input().split())
for _ in range(cin()):
	(n, m) = mi()
	k = pow(2, m) - n
	ans = (k - 1) // 2
	d = set()
	for i in range(n):
		a = int(input(), 2)
		if a <= ans:
			ans += 1
			while ans in d:
				ans += 1
		d.add(a)
	ans = bin(ans)[2:]
	print('0' * (m - len(ans)) + ans)


import sys, heapq
from collections import *
from functools import lru_cache
sys.setrecursionlimit(10 ** 6)
import bisect

def main():
	t = int(input())
	for _ in range(t):
		(n, m) = map(int, input().split(' '))
		total = 2 ** m
		target = (total - n - 1) // 2
		removes = []
		for _ in range(n):
			s = input()
			cur = 0
			for ch in s:
				cur = cur << 1
				if ch == '1':
					cur += 1
			removes.append(cur)
		removes.sort()
		(lo, hi) = (0, 2 ** m - 1)
		while lo <= hi:
			mid = (lo + hi) // 2
			i = bisect.bisect_left(removes, mid)
			if mid - i <= target:
				lo = mid + 1
			else:
				hi = mid - 1
		res = []
		for i in range(m):
			if hi & 1 << i:
				res.append('1')
			else:
				res.append('0')
		print(''.join(res[::-1]))
main()


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	med = (2 ** m - 1) // 2
	l = 2 ** m
	been = {}
	for i in range(n):
		s = int(input(), 2)
		been[s] = 1
		if s == med:
			med += -1 if l % 2 else 1
			while been.get(med):
				med += -1 if l % 2 else 1
		elif s < med and l % 2 == 0:
			med += 1
			while been.get(med):
				med += 1
		elif s > med and l % 2:
			med -= 1
			while been.get(med):
				med -= 1
		l -= 1
	print('0' * (m - len(bin(med)) + 2) + bin(med)[2:])


import math
import string
t = int(input())
for tt in range(t):
	(n, m) = map(int, input().split())
	a = []
	for i in range(n):
		a.append(int(input(), 2))
	need = (2 ** m - n - 1) // 2
	l = 0
	r = 2 ** m
	while r - l > 1:
		mid = (l + r) // 2
		x = mid
		for i in range(n):
			if a[i] < mid:
				x -= 1
		if x > need:
			r = mid
		else:
			l = mid
	ans = []
	for i in range(m):
		ans.append(l % 2)
		l //= 2
	ans.reverse()
	for i in range(m):
		print(ans[i], end='')
	print()


def count_smaller(value, banlist):
	total = value
	for v in banlist:
		if v < value:
			total -= 1
	return total
cases = int(input())
for case in range(cases):
	(n, m) = map(int, input().split())
	banned = []
	for i in range(n):
		banned.append(int(input(), 2))
	desindex = ((1 << m) - n - 1) // 2
	candid = desindex
	while count_smaller(candid, banned) < desindex or candid in banned:
		candid += 1
	print(bin(candid)[2:].zfill(m))


t = int(input())
while t != 0:
	t -= 1
	(n, m) = map(int, input().split())
	p = 2 ** m
	median = (p - n - 1) // 2
	a = []
	for _ in range(n):
		s = int(input(), 2)
		a.append(s)
	a.sort()
	for i in a:
		if i <= median:
			median += 1
	while median in a:
		median += 1
	ans = bin(median)[2:]
	for i in range(m - len(ans)):
		ans = '0' + ans
	print(ans)


for t in range(int(input())):
	(n, m) = map(int, input().split())
	rem = []
	real_rem = []
	med = 2 ** (m - 1) - 1
	for i in range(n):
		iii = input()
		rem.append(int(iii, 2))
	even = True
	while rem:
		cur = rem[0]
		real_rem += [cur]
		rem = rem[1:]
		if even:
			if med < cur:
				pass
			else:
				med += 1
				while med in real_rem:
					med += 1
		elif med <= cur:
			med -= 1
			while med in real_rem:
				med -= 1
		else:
			pass
		even = not even
	print(bin(med)[2:].rjust(m, '0'))


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	a = [int(input(), 2) for _ in range(n)]
	ans = (2 ** m - n - 1) // 2
	for s in sorted(a):
		if s <= ans:
			ans += 1
	ans = bin(ans)
	ans = ans[2:]
	ans = '0' * (m - len(ans)) + ans
	print(ans)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = [None] * n
	for i in range(n):
		a[i] = input()
		a[i] = int(a[i], 2)
	now = 2 ** (m - 1) - 1
	lr = (2 ** m - n - 1) // 2 + 1
	while True:
		(e, le) = (0, now + 1)
		for i in range(n):
			if a[i] <= now:
				le = le - 1
				if a[i] == now:
					e = e + 1
		if le == lr and e == 0:
			ans = ''
			for i in range(m):
				ans = ans + chr(now % 2 + ord('0'))
				now = now // 2
			for i in range(m):
				print(ans[m - i - 1], end='')
			print()
			break
		elif le < lr:
			now = now + 1
		else:
			now = now - 1


import sys
from collections import defaultdict as dd

def eprint(*args):
	print(*args, file=sys.stderr)
zz = 1
from math import *
import copy
if zz:
	input = sys.stdin.readline
else:
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('all.txt', 'w')

def li():
	return [int(x) for x in input().split()]

def fi():
	return int(input())

def si():
	return list(input().rstrip())

def mi():
	return map(int, input().split())

def bo(i):
	return ord(i) - ord('a')
import copy
t = fi()
while t > 0:
	t -= 1
	(n, m) = mi()
	d = {}
	mid = 2 ** (m - 1) - 1
	l = 2 ** m
	for i in range(n):
		s = input().rstrip()
		z = int(s, 2)
		d[z] = 1
		if l % 2 == 1:
			if z >= mid:
				mid -= 1
				while mid in d:
					mid -= 1
			elif z < mid:
				pass
		elif z > mid:
			pass
		else:
			mid += 1
			while mid in d:
				mid += 1
		l -= 1
	r = bin(mid)[2:]
	print((m - len(r)) * '0' + r)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	x = pow(2, m - 1) - 1
	cou = x * 2
	se = set()
	for _ in range(n):
		y = int(input(), 2)
		se.add(y)
		if y >= x and cou % 2 == 1:
			x -= 1
			while x in se:
				x -= 1
		elif y <= x and cou % 2 == 0:
			x += 1
			while x in se:
				x += 1
		cou -= 1
	tt = bin(x)[2:]
	print('0' * (m - len(tt)) + tt)


T = int(input())
for _ in range(T):
	(N, M) = map(int, input().split())
	binary = {int(input(), 2) for _ in range(N)}
	ALL = 1 << M
	L = -1
	R = ALL
	K = (ALL - N) // 2
	half_or_bigger = lambda x: ALL - x - sum((1 if bina > x else 0 for bina in binary)) - 1
	while R - L > 1:
		mid = (R + L) // 2
		if half_or_bigger(mid) >= K:
			L = mid
		else:
			R = mid
	while L in binary:
		L -= 1
	print(bin(L)[2:].zfill(M))


import sys
from collections import deque, defaultdict as dd
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from itertools import permutations
from datetime import datetime
from math import ceil, sqrt, log, gcd

def ii():
	return int(input())

def si():
	return input()

def mi():
	return map(int, input().split())

def li():
	return list(mi())
abc = 'abcdefghijklmnopqrstuvwxyz'
abd = {'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9, 'k': 10, 'l': 11, 'm': 12, 'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18, 't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24, 'z': 25}
mod = 1000000007
inf = float('inf')
vow = ['a', 'e', 'i', 'o', 'u']
(dx, dy) = ([-1, 1, 0, 0], [0, 0, 1, -1])

def read():
	tc = 0
	if tc:
		input = sys.stdin.readline
	else:
		sys.stdin = open('input1.txt', 'r')
		sys.stdout = open('output1.txt', 'w')

def solve():
	for _ in range(ii()):
		(n, m) = mi()
		tot = pow(2, m) - n
		x = (tot - 1) // 2
		a = []
		for i in range(n):
			s = si()
			a.append(int(s, 2))
		a.sort()
		cnt = bisect(a, x)
		x += cnt
		c = cnt
		while cnt:
			cnt = bisect(a, x) - c
			x += cnt
			c += cnt
		s = bin(x)[2:]
		print('0' * (m - len(s)) + s)
solve()


for o in range(int(input())):
	(n, m) = map(int, input().split())
	M = 1 << m
	s = []
	for i in range(n):
		a = input()
		s.append(a)
	l = max(0, M // 2 - 110)
	r = min(M - 1, M // 2 + 110)
	A = [int(a, 2) for a in s]
	for md in range(l, r + 1):
		if md in A:
			continue
		smaller = md
		for a in A:
			if a < md:
				smaller -= 1
		if smaller == (M - len(s) - 1) // 2:
			print(bin(md + M)[3:])


import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import ceil, floor, gcd, fabs, factorial, fmod, sqrt, inf, log, pi, sin
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
mod = pow(10, 9) + 7
mod2 = 998244353

def data():
	return sys.stdin.readline().strip()

def out(*var, end='\n'):
	sys.stdout.write(' '.join(map(str, var)) + end)

def l():
	return list(sp())

def sl():
	return list(ssp())

def sp():
	return map(int, data().split())

def ssp():
	return map(str, data().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(n, val) for j in range(m)]
for _ in range(int(data())):
	(n, m) = sp()
	arr = []
	for i in range(n):
		arr.append(int(data(), 2))
	arr.sort()
	required = ((1 << m) - n - 1) // 2
	for i in range(n):
		if arr[i] <= required:
			required += 1
	answer = bin(required)[2:]
	for i in range(m - len(answer)):
		answer = '0' + answer
	out(answer)


import os
import sys
from io import BytesIO, IOBase

def main():
	for _ in range(int(input())):
		(n, m) = map(int, input().split())
		a = []
		for _ in range(n):
			cur = 0
			for x in input():
				cur <<= 1
				if x == '1':
					cur += 1
			a.append(cur)
		a.sort()
		mid = ((1 << m) - n - 1) // 2
		(l, r) = (-1, 1 << m)
		from bisect import bisect_right as ub
		while r - l > 1:
			cur = (l + r) // 2
			if cur - ub(a, cur) + 1 <= mid:
				l = cur
			else:
				r = cur
		ans = r
		print(''.join((str(ans >> i & 1) for i in reversed(range(m)))))
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


t = int(input())
for y in range(t):
	(n, m) = map(int, input().split())
	mid = 2 ** (m - 1) - 1
	d = dict()
	for i in range(n):
		x = int(input(), 2)
		d[x] = 1
		if i % 2 == 0:
			if x <= mid:
				mid += 1
				while mid in d:
					mid += 1
		elif x >= mid:
			mid -= 1
			while mid in d:
				mid -= 1
	t = ''
	for i in range(m - 1, -1, -1):
		x = 2 ** i
		if mid & x:
			t += '1'
		else:
			t += '0'
	print(t)


import math
import sys
input = sys.stdin.readline
t = int(input())

def toDecimal(x):
	value = 0
	for i in x:
		value = 2 * value + ord(i) - ord('0')
	return value

def toBinary(x, m):
	s = ''
	for i in range(m):
		s += str(x % 2)
		x = x // 2
	return s[::-1]
result = []
for case in range(t):
	(n, m) = map(int, input().split())
	a = []
	for i in range(n):
		a.append(toDecimal(input().strip()))
	a.sort()
	(l, r) = (0, 2 ** m)
	position = (r - n - 1) // 2
	while l < r:
		mid = (l + r + 1) // 2
		cnt = mid
		for i in a:
			if i < mid:
				cnt = cnt - 1
		if position >= cnt:
			l = mid
		else:
			r = mid - 1
	result.append(toBinary(l, m))
print('\n'.join(result))


INF = 10 ** 18
t = int(input())
n = int()
m = int()

def bin(x):
	global m
	res = str()
	while x > 0:
		res += str(x % 2)
		x //= 2
	while len(res) < m:
		res += '0'
	return res[::-1]

def get(x):
	res = 0
	x = x[::-1]
	for i in range(len(x)):
		res += 2 ** i * int(x[i])
	return res

def solve():
	(ll, rr) = map(int, input().split())
	global n
	n = ll
	global m
	m = rr
	a = []
	for i in range(n):
		a.append(get(input()))
	a.sort()
	it = 0
	c = max((2 ** m - n) // 2 - 300, 0)
	lm = 2 ** m - 1
	while True:
		while it < n and a[it] < c:
			it += 1
		l = c - it
		r = lm - c - n + it
		if r < l:
			print(bin(c - 1))
			return
		c += 1
for tt in range(t):
	solve()


testcases = int(input())
for _ in range(testcases):
	(n, m) = map(int, input().split())
	d = dict()
	mid = 2 ** (m - 1) - 1
	for i in range(n):
		s = int(input(), 2)
		d[s] = 1
		if i % 2 == 0:
			if s <= mid:
				mid += 1
				while mid in d:
					mid += 1
		elif s >= mid:
			mid -= 1
			while mid in d:
				mid -= 1
	s = '' + bin(mid)
	s = s[2:]
	if len(s) < m:
		s = '0' * (m - len(s)) + s
	print(s)


import math
testcase = int(input())
for i in range(testcase):
	(n, m) = map(int, input().split())
	li = []
	for j in range(n):
		li.append(int(input(), 2))
	median = 2 ** (m - 1) - 1
	var = 2
	p = 0
	dic = {}
	while p < n:
		if li[p] < median and var % 2 == 0:
			median += 1
			while median in dic:
				median = median + 1
		elif li[p] > median and var % 2 != 0:
			median -= 1
			while median in dic:
				median -= 1
		elif li[p] == median and var % 2 == 0:
			median += 1
			while median in dic:
				median += 1
		elif li[p] == median and var % 2 != 0:
			median -= 1
			while median in dic:
				median -= 1
		dic[li[p]] = 0
		var += 1
		p += 1
	res = ''
	while median:
		res += '1' if median & 1 else '0'
		median >>= 1
	while len(res) < m:
		res += '0'
	res = res[::-1]
	print(res)


import math
T = int(input())
for _ in range(T):
	(n, m) = map(int, input().split())
	arr = []
	Dict = {}
	for i in range(n):
		A = int(input(), 2)
		arr.append(A)
	arr.sort()
	mid = (2 ** m - 1) // 2
	leng = 2 ** m
	for i in arr:
		Dict[i] = 1
		if leng % 2 == 0:
			if i <= mid:
				mid += 1
				while mid in Dict:
					mid += 1
		elif i >= mid:
			mid -= 1
			while mid in Dict:
				mid -= 1
		leng -= 1
	ans = '{0:b}'.format(mid)
	l = m - len(ans)
	ans = '0' * l + ans
	print(ans)


def convert(z):
	s = ''
	while z > 0:
		if z % 2:
			s = '1' + s
		else:
			s = '0' + s
		z = z // 2
	return s

def num(s):
	sumi = 0
	for i in s:
		sumi = 2 * sumi + int(i)
	return sumi

def f(x):
	global lfi
	does = 0
	count = 0
	for i in lfi:
		if i == x:
			does = 1
		if i < x:
			count += 1
	return (count, does)

def binary_search(left, right, req):
	mid = (left + right) // 2
	t = f(mid)
	if mid - t[0] == req and t[1] == 0:
		return mid
	if mid - t[0] <= req:
		return binary_search(mid + 1, right, req)
	return binary_search(left, mid - 1, req)
t = int(input())
for you in range(t):
	l = input().split()
	n = int(l[0])
	m = int(l[1])
	lfi = []
	for i in range(n):
		s = input()
		no = num(s)
		lfi.append(no)
	req = (pow(2, m) - n - 1) // 2
	zo = binary_search(0, pow(2, m) - 1, req)
	z = convert(zo)
	for i in range(m - len(z)):
		print('0', end='')
	print(z)


def binary_number(line):
	count = len(line)
	number = 0
	degree = 0
	for x in range(count):
		if line[x] == '1':
			number += pow(2, count - 1 - degree)
		degree += 1
	return number

def binary_line(number, long):
	line = ''
	for x in range(long):
		if number % 2 == 1:
			line = '1' + line
		else:
			line = '0' + line
		number = number // 2
	return line
tests = int(input())
for i in range(tests):
	numbers = input().split()
	n = int(numbers[0])
	m = int(numbers[1])
	deleted = []
	position = (pow(2, m) - n - 1) // 2
	for x in range(n):
		deleted.append(binary_number(input()))
	deleted.sort()
	for x in range(len(deleted)):
		if deleted[x] <= position:
			position += 1
		else:
			break
	print(binary_line(position, m))


from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush, heappop
import math
from collections import *
from functools import reduce, cmp_to_key, lru_cache
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
M = mod = 10 ** 9 + 7

def factors(n):
	return sorted(set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0))))

def inv_mod(n):
	return pow(n, mod - 2, mod)

def li():
	return [int(i) for i in input().rstrip().split()]

def st():
	return str(input().rstrip())[2:-1]

def val():
	return int(input().rstrip())

def li2():
	return [str(i)[2:-1] for i in input().rstrip().split()]

def li3():
	return [int(i) for i in st()]
for _ in range(val()):
	(n, m) = li()
	l = []
	for i in range(n):
		l.append(int(st(), 2))
	l.sort()
	totrem = 2 ** m - n - 1
	need = totrem // 2
	incre = 0
	while incre != br(l, need):
		incre += 1
		need += 1
	ans = bin(need)[2:]
	ans = '0' * 65 + ans
	ans = ans[-m:]
	print(ans)


from sys import stdin, stdout
import math
import bisect
from collections import defaultdict
_ = int(stdin.readline().strip())
for __ in range(_):
	(n, m) = map(int, stdin.readline().strip().split())
	arr = []
	for i in range(n):
		arr.append(int(stdin.readline().strip(), 2))
	arr.sort()
	ans = ((1 << m) - n - 1) // 2
	for each in arr:
		if each <= ans:
			ans += 1
	ans = bin(ans)[2:]
	ans = '0' * (m - len(ans)) + ans + '\n'
	stdout.writelines(ans)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	binaryString = []
	for _ in range(n):
		binaryString.append(input())
	if m <= 8:
		isIncluded = [True] * 2 ** m
		for val in binaryString:
			isIncluded[int(val, 2)] = False
		curIndex = 0
		medianIndex = 2 ** (m - 1) - n // 2 - 1
		ans = -1
		for i in range(len(isIncluded)):
			if isIncluded[i] == True and curIndex == medianIndex:
				ans = i
				break
			if isIncluded[i] == True:
				curIndex += 1
		res = bin(ans)[2:]
		res = '0' * (m - len(res)) + res
		print(res)
	else:
		isIncluded = [True] * 512
		minusOB = 0
		plusOB = 0
		for val in binaryString:
			if val[0] == '0':
				indicator = False
				for i in range(1, m - 8):
					if val[i] == '0':
						minusOB += 1
						indicator = True
						break
				if not indicator:
					isIncluded[int(val[-8:], 2)] = False
			else:
				indicator = False
				for i in range(1, m - 8):
					if val[i] == '1':
						plusOB += 1
						indicator = True
						break
				if not indicator:
					isIncluded[256 + int(val[-8:], 2)] = False
		curIndex = 0
		medianIndex = 256 + minusOB - n // 2 - 1
		isMedianInMinus = False
		for i in range(512):
			if isIncluded[i] == True and curIndex == medianIndex:
				ans = i
				break
			if isIncluded[i] == True:
				curIndex += 1
		if ans < 256:
			res = bin(ans)[2:]
			res = '0' + '1' * (m - 1 - len(res)) + res
			print(res)
		else:
			res = bin(ans - 256)[2:]
			res = '1' + '0' * (m - 1 - len(res)) + res
			print(res)


def quick_gcd(a, b):
	for i in range(min(a, b), 0, -1):
		if a % i == 0 and b % i == 0:
			return i

def go():
	(n, m) = map(int, input().split())
	s = [int(input(), 2) for _ in range(n)]
	sets = set()
	v = (2 ** m - 1 - n) // 2
	for ss in s:
		if ss <= v:
			v += 1
			while v in sets:
				v += 1
		sets.add(ss)
	res = bin(v)[2:]
	return '0' * (m - len(res)) + res
t = int(input())
ans = []
for _ in range(t):
	ans.append(str(go()))
print('\n'.join(ans))


import sys
import math
import collections

def set_debug(debug_mode=False):
	if debug_mode:
		fin = open('input.txt', 'r')
		sys.stdin = fin
t = int(input())
for ti in range(1, t + 1):
	(n, m) = map(int, input().split())
	x = (2 ** m - n - 1) // 2
	(l, r) = (0, 0)
	arr = []
	for i in range(n):
		arr.append(int(input(), 2))
	arr.sort()
	for i in range(0, n):
		if arr[i] <= x:
			x += 1
	while x in arr:
		x += 1
	y = bin(x)[2:]
	print('0' * (m - len(y)) + y)


def rs():
	return input().strip()

def ri():
	return int(input())

def ria():
	return list(map(int, input().split()))

def ia_to_s(a):
	return ' '.join([str(s) for s in a])

def how_many(m, a, pre, j):
	return 2 ** (m - 1 - j) - sum([1 for x in a if x.startswith(pre) and x[j] == '0'])

def solve(n, m, a):
	k = (2 ** m - n + 1) // 2
	s = ''
	for j in range(m):
		x = how_many(m, a, s, j)
		if x >= k:
			s += '0'
		else:
			s += '1'
			k -= x
	return s

def main():
	for _ in range(ri()):
		(n, m) = ria()
		a = []
		for __ in range(n):
			a.append(rs())
		print(solve(n, m, a))
main()


def solve():
	(n, m) = map(int, input().split())
	a = [int(input(), 2) for _ in range(n)]
	a = sorted(a)
	Del = {}

	def push(x):
		Del[x] = 1

	def process(cur, dx):
		cur += dx
		while cur in Del:
			cur += dx
		return cur
	mean = (1 << m - 1) - 1
	cur = 0
	for x in a:
		if cur == 0:
			if x <= mean:
				mean = process(mean, 1)
		elif x >= mean:
			mean = process(mean, -1)
		push(x)
		cur = (cur + 1) % 2
	l = len(bin(mean)[2:])
	print('0' * (m - l) + bin(mean)[2:])
for _ in range(int(input())):
	solve()


def solve():
	(n, m) = map(int, input().split())
	a_s = [int(input(), 2) for _ in range(n)]
	total = 2 ** m - n
	med = (total + 1) // 2
	l = -1
	r = 2 ** m
	while r - l > 1:
		mid = (r + l) // 2
		cnt = mid + 1
		for a in a_s:
			if a <= mid:
				cnt -= 1
		if cnt >= med:
			r = mid
		else:
			l = mid
	print(format(r, 'b').zfill(m))
for _ in range(int(input())):
	solve()


from sys import stdout, stdin
print = stdout.write
input = stdin.readline

def solve():
	(n, m) = map(int, input().split())
	x = pow(2, m - 1) - 1
	cou = x * 2
	se = set()
	for _ in range(n):
		y = int(input().strip(), 2)
		se.add(y)
		if y >= x and cou % 2 == 1:
			x -= 1
			while x in se:
				x -= 1
		elif y <= x and cou % 2 == 0:
			x += 1
			while x in se:
				x += 1
		cou -= 1
	tt = bin(x)[2:]
	print('0' * (m - len(tt)) + tt + '\n')

def main():
	for t in range(int(input())):
		solve()
main()


def lene(st, le):
	ans = ''
	for i in range(le - len(st)):
		ans += '0'
	ans = ans + st
	return ans
a = int(input())
for i in range(a):
	(x, y) = map(int, input().split())
	from collections import defaultdict
	count = 0
	mid = pow(2, y) // 2 - 1
	al = defaultdict(int)
	for i in range(x):
		r = input()
		r = int(r, 2)
		if count % 2 == 0:
			count += 1
			al[r] = 1
			if r <= mid:
				al[r] = 1
				mid += 1
				while al[mid] != 0:
					mid += 1
		else:
			count += 1
			al[r] = 1
			if r >= mid:
				al[r] = 1
				mid -= 1
				while al[mid] != 0:
					mid -= 1
	u = bin(mid)
	u = u[2:]
	print(lene(u, y))


from bisect import bisect_left
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	A = []
	G = set()
	for __ in range(n):
		kek = int(input(), 2)
		A.append(kek)
		G.add(kek)
	A.sort()
	k = 2 ** m - n
	k = (k - 1) // 2
	ans = -1
	for num in range(2 ** (m - 1) - 2 * n - 20, 2 ** (m - 1) + 2 * n + 20):
		if 0 <= num < 2 ** m:
			lol = num - bisect_left(A, num + 1)
			if lol == k and num not in G:
				ans = num
				break
	l = ans
	print(str(bin(l))[2:].zfill(m))


import sys

def input():
	return sys.stdin.readline().strip()

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST(N=None):
	return list(MAP()) if N is None else [INT() for i in range(N)]

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
INF = 10 ** 19
MOD = 10 ** 9 + 7
for _ in range(INT()):
	(N, M) = MAP()
	A = [int(input(), 2) for i in range(N)]
	mid = 2 ** M // 2 - 1
	used = set()
	ln = 2 ** M
	for a in A:
		if a <= mid and ln % 2 == 0:
			tmp = mid + 1
			while tmp in used:
				tmp += 1
			mid = tmp
		if a >= mid and ln % 2 == 1:
			tmp = mid - 1
			while tmp in used:
				tmp -= 1
			mid = tmp
		used.add(a)
		ln -= 1
	ans = format(mid, 'b').zfill(M)
	print(ans)