Madoka finally found the administrator password for her computer. Her father is a well-known popularizer of mathematics, so the password is the answer to the following problem.

Find the maximum decimal number without zeroes and with no equal digits in a row, such that the sum of its digits is $n$.

Madoka is too tired of math to solve it herself, so help her to solve this problem!


-----Input-----

Each test contains multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases. Description of the test cases follows.

The only line of each test case contains an integer $n$ ($1 \le n \le 1000$) — the required sum of the digits.


-----Output-----

For each test case print the maximum number you can obtain.


-----Examples-----

Input
5
1
2
3
4
5
Output
1
2
21
121
212


-----Note-----

The only numbers with the sum of digits equal to $2$ without zeros are $2$ and $11$. But the last one has two ones in a row, so it's not valid. That's why the answer is $2$.

The only numbers with the sum of digits equal to $3$ without zeros are $111$, $12$, $21$, and $3$. The first one has $2$ ones in a row, so it's not valid. So the maximum valid number is $21$.

The only numbers with the sum of digits equals to $4$ without zeros are $1111$, $211$, $121$, $112$, $13$, $31$, $22$, and $4$. Numbers $1111$, $211$, $112$, $22$ aren't valid, because they have some identical digits in a row. So the maximum valid number is $121$.

Difficulty: EASY
Tags: Mathematics

Implementation

Starter code:

Solutions:
for t in range(int(input())):
	x = 387420489
	n = int(input())
	if n < 3:
		print(n)
	else:
		a = '21' * (n // 3)
		if n % 3 == 1:
			print('1' + a)
		elif n % 3 == 0:
			print(a)
		else:
			print(a + '2')


T = int(input())
for t in range(T):
	n = int(input())
	if n == 1:
		print(1)
		continue
	if n == 2:
		print(2)
		continue
	if n % 3 == 0:
		print('21' * (n // 3))
		continue
	if n % 3 == 2:
		x = '21' * ((n + 1) // 3)
		print(x[:len(x) - 1])
		continue
	x = '12' * ((n + 2) // 3)
	print(x[:len(x) - 1])


t = int(input())
for test in range(t):
	n = int(input())
	t3 = n // 3
	maxim = '21'
	out = ''
	out = maxim * t3
	if n % 3 == 1:
		out = '1' + out
	elif n % 3 == 2:
		out = out + '2'
	print(out)


for n in [*map(int, open(0))][1:]:
	r = n % 3
	print(n // 3 * ('21', '12')[r == 1], r or '', sep='')


t = int(input())
for i in range(t):
	n = int(input())
	if n % 3 == 0:
		m = n // 3
		print('21' * m)
	elif n % 3 == 1:
		m = n // 3
		print('12' * m + '1')
	elif n % 3 == 2:
		m = n // 3
		print('21' * m + '2')


for _ in range(int(input())):
	n = int(input())
	x = '21'
	m = n % 3
	a = n // 3
	print((m == 1) * (x[::-1] * (a + 1))[:-1] + (m == 2) * (x * (a + 1))[:-1] + (m == 0) * x * a)


testcase = input()
testcase = int(testcase)
for i in range(testcase):
	num = input()
	num = int(num)
	if num == 1:
		print('1')
		continue
	if num == 2:
		print('2')
		continue
	if num % 3 == 0:
		print('21' * (num // 3))
	elif num % 3 == 1:
		print('1' + '21' * (num // 3))
	elif num % 3 == 2:
		print('21' * (num // 3) + '2')


k = []
for i in range(int(input())):
	n = int(input())
	if n % 3 == 0:
		s = '21' * (n // 3)
	elif n % 3 == 1:
		s = '12' * (n // 3) + '1'
	else:
		s = '21' * (n // 3) + '2'
	k.append(s)
for t in k:
	print(t)


for i in range(0, int(input())):
	n = int(input())
	if n == 1:
		print(1)
	elif n == 2:
		print(2)
	else:
		s = '21' * (n // 3)
		if n % 3 == 1:
			s = '1' + s
		elif n % 3 == 2:
			s = s + '2'
		print(s)


for _ in range(int(input())):
	n = int(input())
	if n % 3 == 0:
		ans = '21' * (n // 3)
	elif n % 3 == 1:
		ans = '1' + '21' * (n // 3)
	else:
		ans = '21' * (n // 3) + '2'
	print(ans)


for _ in range(int(input())):
	n = int(input())
	ans = '21' * (n // 3)
	if n % 3 == 2:
		ans += '2'
	if n % 3 == 1:
		ans = '1' + ans
	print(ans)


for _ in range(int(input())):
	n = int(input())
	if n % 3 == 0:
		print('21' * (n // 3))
	if n % 3 == 1:
		print('12' * (n // 3) + '1')
	if n % 3 == 2:
		print('21' * (n // 3) + '2')


t = int(input())

def q(n):
	q = n // 3
	v = n % 3
	if v == 1:
		s = '1'
		s += '21' * q
	elif v == 2:
		s = '21' * q
		s += '2'
	else:
		s = '21' * q
	return s
for i in range(t):
	n = int(input())
	print(q(n))


inpt = int(input())
for i in range(inpt):
	a = int(input())
	if a % 3 == 1:
		print('1' + (a - 1) // 3 * '21')
	elif a % 3 == 2:
		print((a - 2) // 3 * '21' + '2')
	else:
		print(a // 3 * '21')


inp1 = int(input())
list1 = []
for i in range(inp1):
	inp2 = int(input())
	if inp2 % 3 == 0:
		print('21' * (inp2 // 3))
	elif inp2 % 3 == 1:
		print(str(1) + '21' * (inp2 // 3))
	elif inp2 % 3 == 2:
		print('21' * (inp2 // 3) + str(2))


t = int(input())
while t > 0:
	n = int(input())
	if n == 1 or n == 2:
		print(n)
	else:
		if n % 3 == 2:
			s = '21' * (n // 3)
			s += '2'
		if n % 3 == 1:
			s = '12' * (n // 3)
			s += '1'
		if n % 3 == 0:
			s = '21' * (n // 3)
		print(s)
	t -= 1


for x in range(int(input())):
	n = int(input())
	x = n % 3
	n = n // 3
	s = '21' * n
	if x == 1:
		s = '1' + s
	elif x == 2:
		s += '2'
	print(s)


for i in range(int(input())):
	number = int(input())
	if number == 1:
		print(number)
	elif number == 2:
		print(number)
	elif number % 3 == 0:
		print('21' * (number // 3))
	elif number % 3 == 1:
		print('12' * (number // 3) + '1')
	elif number % 3 == 2:
		print('21' * (number // 3) + '2')


for i in range(int(input())):
	n = int(input())
	if n % 3 == 1:
		print('12' * (n // 3) + '1')
	elif n % 3 == 2:
		print('21' * (n // 3) + '2')
	else:
		print('21' * (n // 3))


for i in range(int(input())):
	n = int(input())
	if n == 1 or n == 2:
		print(n)
	elif n % 3 == 0:
		print('21' * (n // 3))
	elif n % 3 == 1:
		print('12' * (n // 3) + '1')
	elif n % 3 == 2:
		print('21' * (n // 3) + '2')


ran = int(input())

def fun(target):
	if target % 3 == 0:
		return '21' * int(target / 3)
	elif target % 3 == 1:
		return '1' + '21' * int(target / 3)
	elif target % 3 == 2:
		return '21' * int(target / 3) + '2'
for x in range(1, ran + 1):
	target = int(input())
	print(fun(target))


t = int(input())
for i in range(t):
	n = int(input())
	count1 = n // 3
	count2 = n % 3
	if count2 == 2:
		print('2' + '12' * count1)
	else:
		print('1' * count2 + '21' * count1)


n = int(input())

def Long_sum(a):
	if a % 3 == 0:
		print('21' * int(a / 3))
		return
	elif a % 3 == 1:
		print('12' * int(a // 3) + '1')
		return
	else:
		print('21' * int(a // 3) + '2')
		return
for i in range(n):
	a = int(input())
	Long_sum(a)


for _ in range(int(input())):
	x = int(input())
	if x == 1:
		print(1)
		continue
	elif x == 2:
		print(2)
		continue
	if x % 3 == 0:
		print(str(21) * (x // 3))
	elif x % 3 == 1:
		print(str(12) * (x // 3) + str(1))
	else:
		print(str(21) * (x // 3) + str(2))


import math
t = int(input())
for i in range(t):
	n = int(input())
	if n % 3 == 0:
		print('21' * math.floor(n / 3))
	elif n % 3 == 1:
		print('12' * math.floor(n / 3) + '1')
	else:
		print('21' * math.floor(n / 3) + '2')


for t in range(int(input())):
	N = int(input())
	Rem = N % 3
	C = N // 3
	if Rem == 2:
		print('21' * C + '2')
	elif Rem == 0:
		print('21' * C)
	else:
		print('12' * C + '1')


for inh in range(int(input())):
	n = int(input())
	if n % 3 == 0:
		ans = '21' * (n // 3)
	elif n % 3 == 2:
		ans = '21' * (n // 3)
		ans += '2'
	else:
		ans = '12' * (n // 3)
		ans += '1'
	print(ans)


for _ in range(int(input())):
	n = int(input())
	d = ''
	if n % 3 == 0:
		d = '21' * (n // 3)
	elif n % 3 == 1:
		d = '12' * (n // 3) + '1'
	else:
		d = '21' * (n // 3) + '2'
	print(d)


from sys import stdin
from math import log, floor, ceil, gcd
from collections import defaultdict as dd
input = stdin.readline
inp = lambda : int(stdin.readline())
rs = lambda : stdin.readline().strip()

def ra(typ):
	return list(map(typ, stdin.readline().split()))

def rv(typ):
	return map(typ, stdin.readline().split())

def main():
	for _ in range(inp()):
		n = inp()
		x = n % 3
		if n == 1:
			print(1)
		elif n == 2:
			print(2)
		elif x == 0:
			print('21' * (n // 3))
		elif x == 1:
			print('12' * (n // 3) + '1')
		else:
			print('21' * (n // 3) + '2')
main()


def solve_one():
	n = int(input())
	mod = n % 3
	if mod == 0:
		print('21' * (n // 3))
	elif mod == 1:
		print('1', '21' * (n // 3), sep='')
	elif mod == 2:
		print('21' * (n // 3), '2', sep='')

def solve():
	t = int(input())
	for _ in range(t):
		solve_one()
solve()


for g in [*map(int, open(0))][1:]:
	s = g % 3
	print(g // 3 * ('21', '12')[s == 1], s or '', sep='')


for _ in range(int(input())):
	num = int(input())
	div = num // 3
	res = ''
	if num % 3 == 1:
		res = '1'
		res += '21' * div
	elif num % 3 == 0:
		res = '21' * div
	else:
		res = '2' + '12' * div
	print(res)


import string
letters = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
t = int(input())
for _ in range(t):
	n = int(input())
	if n % 3 == 0:
		print(f"{n // 3 * '21'}")
	elif n % 3 == 1:
		print(f"1{n // 3 * '21'}")
	else:
		print(f"{n // 3 * '21'}2")


n = int(input())
l = []
for i in range(n):
	a = int(input())
	l.append(a)
l.sort()

def rem_3(x):
	if x % 3 == 0:
		return 0
	elif x % 3 == 1:
		return 1
	else:
		return 2
for i in range(n):
	if rem_3(l[i]) == 0:
		print('21' * (l[i] // 3))
	elif rem_3(l[i]) == 1:
		print('1' + '21' * ((l[i] - 1) // 3))
	else:
		print('2' + '12' * ((l[i] - 1) // 3))


t = int(input())
for tc in range(t):
	n = int(input())
	if n % 3 == 0:
		print(n // 3 * '21')
	elif n % 3 == 1:
		print('1' + n // 3 * '21')
	else:
		print('2' + n // 3 * '12')


from collections import Counter

def read_single_num():
	return int(input())

def read_nums():
	return [int(x) for x in input().split()]
t = read_single_num()
for i in range(t):
	n = read_single_num()
	if n == 1:
		print(1)
	elif n == 2:
		print(2)
	elif n % 3 == 0:
		print('21' * (n // 3))
	elif n % 3 == 1:
		print('12' * (n // 3) + '1')
	else:
		print('21' * (n // 3) + '2')


for _ in range(int(input())):
	n = int(input())
	k = n // 3
	m = n % 3
	if m == 1:
		print('12' * k, end='')
		print(m)
	elif m == 2:
		print('21' * k + '2')
	else:
		print('21' * k)


t = int(input())
for _ in range(t):
	n = int(input())
	res = []
	if n == 1:
		print('1')
	else:
		k = n // 3
		if n % 3 == 0:
			print('21' * k)
		elif n % 3 == 1:
			print('1' + '21' * k)
		else:
			print('2' + '12' * k)


for tst in range(int(input())):
	n = int(input())
	if n % 3 == 0:
		print('21' * (n // 3))
	elif n % 3 == 1:
		print('12' * (n // 3) + '1')
	else:
		print('21' * (n // 3) + '2')


t = int(input())
for i in range(t):
	n = int(input())
	if n % 3 == 0:
		st = '21' * (n // 3)
		print(st)
	elif n % 3 == 1:
		st = '1'
		st += '21' * (n // 3)
		print(st)
	else:
		st = '21' * (n // 3)
		st += '2'
		print(st)


import math

def intlist():
	return [int(i) for i in input().split(' ')]

def stringlist():
	return input().split(' ')

def yes(t):
	if t:
		return 'YES'
	return 'NO'

def printjoin(l):
	l = [str(i) for i in l]
	return ' '.join(l)

def power_of_two(n):
	b = bin(n)[2:]
	return int(b) == 10 ** (len(b) - 1)

def bit_count(n):
	return bin(n).count('1')

def solve():
	n = int(input())
	if n == 1:
		return 1
	if n == 2:
		return 2
	if n % 3 == 0:
		return '21' * int(n // 3)
	elif n % 3 == 2:
		return '21' * int(n // 3) + '2'
	else:
		return '12' * int(n // 3) + '1'
	return ''
t = input()
for tt in range(int(t)):
	print(solve())


def sol(num):
	if num % 3 == 0:
		return '21' * (num // 3)
	if num % 3 == 1:
		return '1' + '21' * (num // 3)
	return '2' + '12' * (num // 3)
for _ in range(int(input())):
	print(sol(int(input())))


t = int(input())
for _ in range(t):
	n = int(input())
	(ones, twos) = (n // 3, n // 3)
	if n % 3 == 1:
		ones += 1
	if n % 3 == 2:
		twos += 1
	ans = ''
	if ones == twos:
		ans = '21' * ones
	if ones > twos:
		ans = '12' * twos + '1'
	if ones < twos:
		ans = '21' * ones + '2'
	print(ans)


def solve():
	n = int(input())
	remain = n % 3
	ans = '21' * (n // 3)
	if remain == 1:
		ans = '1' + ans
	elif remain == 2:
		ans += '2'
	print(ans)
for tc in range(int(input())):
	solve()


from math import *
from sys import *
from bisect import bisect_left as bl
from bisect import bisect_right as br
from collections import Counter as ctr
from collections import deque as dq
input = stdin.readline
inp = lambda : int(input())
li = lambda : list(map(int, input().split()))
lb = lambda : list(map(int, input()))
ls = lambda : list(input())
bi = lambda n: bin(n).replace('0b', '')
yn = lambda f: print('NYOE S'[f::2])
srp = lambda s, i, c: s[:i] + c + s[i + 1:]

def solve(__=1):
	for _ in range(__):
		n = inp()
		if n % 3 != 1:
			print('21' * (ceil(n / 3) - 1) + '2' + '1' * (n % 3 == 0))
		else:
			print('12' * (n // 3) + '1')
solve(inp())


T = int(input())
for t in range(T):
	N = int(input())
	Q = N // 3
	R = N % 3
	ans = ''
	if R == 0:
		ans = '21' * Q
	elif R == 1:
		ans = '12' * Q + '1'
	else:
		ans = '21' * Q + '2'
	print(ans)


import sys
import math
__ = int(sys.stdin.readline())
d = {}
for i in range(1, 10 ** 4):
	d[i ** 3] = i
for _ in range(__):
	n = int(sys.stdin.readline())
	if n == 1:
		print(1)
	elif n == 2:
		print(2)
	else:
		x = n % 3
		if x == 0:
			print('21' * (n // 3))
		elif x == 1:
			s = '12' * (n // 3)
			print(s + '1')
		else:
			s = '21' * (n // 3)
			print(s + '2')


def solve():
	n = int(input())
	s = '21'
	s = s * (n // 3)
	if n % 3 == 1:
		s = '1' + s
	if n % 3 == 2:
		s = s + '2'
	print(s)
t = int(input())
while t:
	solve()
	t -= 1


for _ in range(int(input())):
	n = int(input())
	res = ''
	res += '21' * (n // 3)
	if n % 3 == 1:
		res = '1' + res
	elif n % 3 == 2:
		res = res + '2'
	print(res)


t = int(input())
for _ in range(t):
	n = int(input())
	tos = n // 3
	rem = n % 3
	if rem == 1:
		print('1' + '21' * tos)
	elif rem == 2:
		print('21' * tos + '2')
	else:
		print('21' * tos)


tc = int(input())
for i in range(tc):
	x = int(input())
	if x % 3 == 0:
		print('21' * (x // 3))
	elif x % 3 == 1:
		print('1' + x // 3 * '21')
	else:
		print(x // 3 * '21' + '2')


def main():
	t = int(input())
	for _ in range(t):
		n = int(input())
		if n % 3 == 1:
			ans = '1' + (n - 1) // 3 * '21'
		if n % 3 == 2:
			ans = '2' + (n - 2) // 3 * '12'
		if n % 3 == 0:
			ans = '21' + (n - 3) // 3 * '21'
		print(ans)
main()


import math
tc = int(input())
for i in range(tc):
	x = int(input())
	r = x % 3
	if r == 0:
		print('21' * (x // 3))
	elif r == 1:
		times = math.floor(x / 3)
		print('12' * times, end='')
		print('1')
	else:
		times = math.floor(x / 3)
		print('21' * times, end='')
		print('2')


case = int(input())
for i in range(case):
	n = int(input())
	r = n % 3
	if r == 0:
		print(int(n / 3) * '21')
	elif r == 1:
		result = '1' + int(n / 3) * '21'
		print(result)
	else:
		result = int(n / 3) * '21' + '2'
		print(result)


d = [None for i in range(1000)]
d[0] = '1'
d[1] = '2'
d[2] = '21'

def f(n):
	n -= 1
	if d[n] == None:
		p = f(n)
		if p[-1] == '2':
			d[n] = p + '1'
		elif p[0] == '2':
			d[n] = '1' + p
		else:
			d[n] = p[1:] + '2'
	return d[n]
for _ in range(int(input())):
	n = int(input())
	print(f(n))


T = int(input())
while T:
	N = int(input())
	print(['21' * (N // 3), '1' + '21' * (N // 3), '21' * (N // 3) + '2'][N % 3])
	T -= 1


t = int(input())
while t != 0:
	t -= 1
	n = int(input())
	if n == 1:
		print(1)
	elif n == 2:
		print(2)
	else:
		k = n // 3
		if n - 3 * k == 0:
			print(k * '21')
		if n - 3 * k == 1:
			print(k * '12' + '1')
		if n - 3 * k == 2:
			print(k * '21' + '2')


T = int(input())
for t in range(T):
	n = int(input())
	val = n // 3
	ans = []
	for i in range(val):
		ans.append('21')
	if n % 3 == 2:
		ans.append('2')
	elif n % 3 == 1:
		ans = ['1'] + ans
	print(''.join(ans))


for i in range(int(input())):
	n = int(input())
	if n == 1:
		print(1)
	elif n == 2:
		print(2)
	elif n == 3:
		print(21)
	elif n == 4:
		print(121)
	elif n == 5:
		print(212)
	elif n % 3 == 0:
		print('21' * (n // 3))
	elif n % 3 == 1:
		print('12' * (n // 3) + '1')
	else:
		print('21' * (n // 3) + '2')


t = int(input())
while t:
	n = int(input())
	if (n + 2) % 3 == 0:
		s = int((n + 2) / 3)
		print(1, end='')
		print('21' * (s - 1))
	elif (n + 3) % 3 == 0:
		d = int((n + 3) / 3) - 1
		print('21' * d)
	elif (n + 1) % 3 == 0:
		f = int((n + 1) / 3) - 1
		print('21' * f, end='')
		print(2)
	t -= 1


T = int(input())
for t in range(T):
	n = int(input())
	ans = '21' * (n // 3)
	if n % 3 == 1:
		ans = '1' + ans
	elif n % 3 == 2:
		ans = ans + '2'
	print(ans)


T = int(input())
for _ in range(T):
	N = int(input())
	A = N // 3
	if N % 3 == 0:
		print('21' * A)
	elif N % 3 == 1:
		print('12' * A + '1')
	else:
		print('21' * A + '2')


t = int(input())
for i in range(t):
	n = int(input())
	s = '21'
	b = n // 3
	if n % 3 == 0:
		print(s * b)
	elif n % 3 == 1:
		print('1' + s * b)
	elif n % 3 == 2:
		print(s * b + '2')


T = int(input())
for t in range(T):
	n = int(input())
	if n % 3 == 0:
		x = n / 3
		print((str(21) + '') * int(x))
	elif (n - 1) % 3 == 0:
		x = n / 3
		print('1' + (str(21) + '') * int(x))
	elif (n - 2) % 3 == 0:
		x = n / 3
		print('2' + (str(12) + '') * int(x))


k = int(input())

def f(x):
	v = x // 2
	return (v, v + x % 2)
for _ in range(k):
	n = int(input())
	o = n % 3
	r = '21' * (n // 3)
	if o == 1:
		r = '1' + r
	elif o == 2:
		r += '2'
	print(r)


t = int(input())
for q in range(t):
	n = int(input())
	if n == 1:
		x = 1
	elif n == 2:
		x = 2
	else:
		k = n // 3
		if n - k * 3 == 2:
			x = '21' * k + '2'
		elif n - k * 3 == 1:
			x = '12' * k + '1'
		else:
			x = '21' * k
	print(x)


t = int(input())
for _ in range(t):
	n = int(input())
	if n == 3:
		print('21')
		continue
	if n % 3 == 2 or n % 3 == 0:
		x = n // 3
		y = n % 3
		str1 = '21' * x
		if y != 0:
			print(str1 + str(y))
		else:
			print(str1)
	elif n % 3 == 1:
		x = n // 3
		str2 = '12' * x
		y = n % 3
		print(str2 + str(y))


for i in range(int(input())):
	n = int(input())
	if n == 1:
		print('1')
	elif n == 2:
		print('2')
	else:
		p = n // 3
		s = '21' * p
		x = n % 3
		if x == 1:
			s = '1' + s
		elif x == 2:
			s += '2'
		print(s)


for i in range(int(input())):
	a = int(input())
	s = '21'
	if a % 3 == 0:
		print(s * (a // 3))
	elif a % 3 == 1:
		print(str(1) + s * (a // 3))
	elif a % 3 == 2:
		print(s * (a // 3) + str(2))


import math
t = int(input())
a = ''
for i in range(t):
	n = int(input())
	a = '21' * (math.floor((n + 1) / 3) - 1) + '2'
	if n == 1:
		a = '1'
	elif not n % 3:
		a += '1'
	elif n % 3 == 1:
		a = '1' + a + '1'
	print(a)