Problem: You are given a positive number x. Find the smallest positive integer number that has the sum of digits equal to x and all digits are distinct (unique).

Input

The first line contains a single positive integer t (1 ≤ t ≤ 50) — the number of test cases in the test. Then t test cases follow.

Each test case consists of a single integer number x (1 ≤ x ≤ 50).

Output

Output t answers to the test cases:

  * if a positive integer number with the sum of digits equal to x and all digits are different exists, print the smallest such number; 
  * otherwise print -1. 

Example

Input


4
1
5
15
50


Output


1
5
69
-1

Solution (in CPP):

Solution:
#include <iostream>
#include <string>
using namespace std;

int main()
{
	int t;
	cin >> t;

	for(int u = 1; u <= t; ++u)
	{
		int x;
		cin >> x;

		if(x > 45)
			cout << -1;
		else
		{
			if(x < 10)
				cout << x;
			else
			{
				if(x == 10)
					cout << 19;
				else if(x == 11)
					cout << 29; 
				else if(x == 12)
					cout << 39; 
				else if(x == 13)
					cout << 49; 
				else if(x == 14)
					cout << 59; 
				else if(x == 15)
					cout << 69; 
				else if(x == 16)
					cout << 79; 
				else if(x == 17)
					cout << 89; 
				else if(x == 18)
					cout << 189; 
				else if(x == 19)
					cout << 289; 
				else if(x == 20)
					cout << 389; 
				else if(x == 21)
					cout << 489; 
				else if(x == 22)
					cout << 589; 
				else if(x == 23)
					cout << 689; 
				else if(x == 24)
					cout << 789; 
				else if(x == 25)
					cout << 1789; 
				else if(x == 26)
					cout << 2789; 
				else if(x == 27)
					cout << 3789; 
				else if(x == 28)
					cout << 4789; 
				else if(x == 29)
					cout << 5789; 
				else if(x == 30)
					cout << 6789; 
				else if(x == 31)
					cout << 16789;
				else if(x == 32)
					cout << 26789;
				else if(x == 33)
					cout << 36789;
				else if(x == 34)
					cout << 46789;
				else if(x == 35)
					cout << 56789;
				else if(x == 36)
					cout << 156789;
				else if(x == 37)
					cout << 256789;
				else if(x == 38)
					cout << 356789;
				else if(x == 39)
					cout << 456789;
				else if(x == 40)
					cout << 1456789;
				else if(x == 41)
					cout << 2456789;
				else if(x == 42)
					cout << 3456789;
				else if(x == 43)
					cout << 13456789;
				else if(x == 44)
					cout << 23456789;
				else if(x == 45)
					cout << 123456789;
			}
		}

		cout << "\n";
	}

	//system("pause");
	return 0;
}