Madoka and Math Dad
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!
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$$$.
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.
For each test case print the maximum number you can obtain.
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()
if __name__ == '__main__':
    solve()
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)
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)