Determine a valid integer having K digits such that the product of digits of the integer is greater than or equal to the sum of digits of the integer and the product of the digits of the integer is minimized. If more than such integer exists, determine the smallest possible integer.

Constraints:

T = 20 (Number of testcases)

K = 10^5 (length of integer)

Examples:

K = 3, return 123

K = 4, return 1124

K = 5, return 11222 (note that answer is not 11125 as product here is 10 while product of 11222 is 8)

Few more testcases:

First line of input contains number of testcases T then T lines follow having an integer K on each line. Out put should be string of the actual Integer.

Input:
13
1
2
3
4
5
6
7
8
9
10
11
20
30

Output:
1
22
123
1124
11222
111126
1111134
11111223
111111135
1111111144
11111111224
11111111111111111333
111111111111111111111111112233

I couldn't come up with any optimal solution, can anyone please help? Thanks!