C. Minimum Varied Number

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Find the minimum number with the given sum of digits ss such that all digits in it are distinct (i.e. all digits are unique).

For example, if s=20s=20, then the answer is 389389. This is the minimum number in which all digits are different and the sum of the digits is 2020 (3+8+9=203+8+9=20).

For the given ss print the required number.

Input

The first line contains an integer tt (1≤t≤451≤t≤45) — the number of test cases.

Each test case is specified by a line that contains the only integer ss (1≤s≤451≤s≤45).

Output

Print tt integers — the answers to the given test cases.

Example

input

Copy

4

20

8

45

10

output

Copy

389
8
123456789
19

解题说明：此题要求数字不重复，n小于10直接输出就行，大于10是先让n从9开始逐一减，直到n满足要求。

#include 
 
int main()
{
	int t, n, digit;
	scanf("%d", &t);
 
	while (t--)
	{
		scanf("%d", &n);
		if (n < 10)
		{
			printf("%d\n", n);
			continue;
		}
 
		digit = 9;
		while (n > digit)
		{
			n -= digit;
			digit--;
		}
 
		printf("%d", n);
		digit++;
 
		while (digit < 10)
		{
			printf("%d", digit++);
		}
		printf("\n");
	}
 
	return 0;
}