Kulyash believes in equality.  
Given an integer N, output a binary string of length N such that:
The count of 01 [subsequences] in the string is equal to the count of 10 subsequences; 
The string has at least one occurrence of 0 as well as 1.

If multiple such strings exist, print any. Also, it is guaranteed that corresponding to the given input, an answer always exists.

------ Input Format ------ 

- First line will contain T, number of test cases. Then the test cases follow.
- Each test case contains of a single line of input, an integer N - the length of the binary string.

------ Output Format ------ 

For each test case, output any binary string of length N satisfying the given conditions.

------ Constraints ------ 

$1 ≤ T ≤ 100$
$3 ≤ N ≤ 1000$

----- Sample Input 1 ------ 
2
4
3

----- Sample Output 1 ------ 
1001
010

----- explanation 1 ------ 
Test case $1$: A binary string satisfying both the conditions is $1001$. The count of $01$ as well as $10$ subsequences in the string is $2$.

Test case $2$: A binary string satisfying both the conditions is $010$. The count of $01$ as well as $10$ subsequences in the string is $1$.

Source: codechef | Difficulty: EASY
Tags: String algorithms

Constructive algorithms

Data structures

Ad-hoc


Solutions:
t = int(input())
for i in range(t):
	n = int(input())
	st = ''
	if n % 2 == 0:
		for j in range(n):
			if j == 0 or j == n - 1:
				st += '1'
			else:
				st += '0'
	else:
		for j in range(n):
			if j == (n - 1) / 2:
				st += '1'
			else:
				st += '0'
	print(st)


T = int(input())
for i in range(T):
	n = int(input())
	l = []
	if n % 2 == 0:
		k = n // 2
		for j in range(k):
			if j % 2 != 0:
				l.append(0)
			else:
				l.append(1)
		for j in range(k, n):
			if j % 2 == 0:
				l.append(0)
			else:
				l.append(1)
	else:
		for j in range(n):
			if j % 2 == 0:
				l.append(0)
			else:
				l.append(1)
	s = ''.join([str(p) for p in l])
	print(s)


for i in range(int(input())):
	n = int(input())
	if n >= 4:
		for i in range(n):
			if i == 0:
				print('1', end='')
			elif i == 1:
				print('0', end='')
			elif i == n - 1:
				print('1', end='')
			elif i == n - 2:
				print('0', end='')
			else:
				print('0', end='')
		print('')
	elif n == 3:
		print('010')


for _ in range(int(input())):
	n = int(input())
	if n % 2 == 0:
		print('1' + (n - 2) * '0' + '1')
	else:
		print('0' + n // 2 * '10')


n = int(input())
for i in range(n):
	a = int(input())
	m = ''
	k = a % 2
	if k == 0:
		m = m + '1'
		for j in range(a - 2):
			m = m + '0'
		m = m + '1'
	else:
		for i in range(a // 2):
			m = m + '0'
		m = m + '1'
		for i in range(a // 2):
			m = m + '0'
	print(m)


def get_stringq(numq):
	if numq % 2 == 0:
		return '1' + '0' * (numq - 2) + '1'
	else:
		return '0' + '10' * (numq // 2)
for i in range(int(input())):
	numq = int(input())
	print(get_stringq(numq))


for _ in range(int(input())):
	N = int(input())
	if N % 2:
		N //= 2
		print('0' * N + '1' + '0' * N)
	else:
		N -= 2
		print('1' + '0' * N + '1')


n = int(input())
for i in range(n):
	x = int(input())
	l = ''
	if x % 2 == 0:
		l += '1'
		for i in range(x - 2):
			l += '0'
		l += '1'
		print(l)
	else:
		k = x // 2
		for i in range(x):
			if i == k:
				l += '1'
			else:
				l += '0'
		print(l)


for _ in range(int(input())):
	n = int(input())
	RET = ''
	if n % 2 == 0:
		RET += '1'
		for i in range(n - 2):
			RET += '0'
		RET += '1'
	else:
		for i in range(n // 2):
			RET += '0'
		RET += '1'
		for i in range(n // 2):
			RET += '0'
	print(RET)


t = int(input())
for i in range(t):
	n = int(input())
	s = ''
	if n % 2 == 1:
		s += '0'
		for j in range(n // 2):
			s += '1'
			s += '0'
	else:
		s += '1'
		for j in range(n // 2 - 1):
			s += '0'
			s += '0'
		s += '0' if s.count('0') <= s.count('1') else '1'
	print(s)


for i in range(int(input())):
	t = int(input())
	if t % 2 == 0:
		print(1, end='')
		for i in range(t - 2):
			print(0, end='')
		print(1, end='')
	else:
		print(0, end='')
		for i in range(t - 2):
			print(1, end='')
		print(0, end='')
	print('\n')