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:
//I
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
using namespace std;
template<typename __T>
inline void read(__T &x)
{
    x=0;
    int f=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')   f=-1;c=getchar();}
    while(isdigit(c))   {x=x*10+c-'0';c=getchar();}
    x*=f;
}
typedef pair<int,int>pi;
pi mp(int a,int b)
{
	return make_pair(a,b);
}
const int mod=1000000007;
long long qpow(long long a,long long b=mod-2)
{
	long long ans=1;
	while(b)
	{
		if(b&1)	ans=ans*a%mod;
		b>>=1;
		a=a*a%mod;
	}
	return ans;
}
bool chk(int sv,int bt)
{
	int sp=bt*(9+9-bt+1)/2;
	return sv<=sp;
}
int main()
{
	int T;
	read(T);
	while(T--)
	{
		int n;
		read(n);
		if(n>45)
		{
			printf("-1\n");
			continue;
		}
		int gp=9;
		while(gp>1 && chk(n,gp-1))	gp--;
		long long ans=0;
		//cout<<"G"<<gp<<endl;
		for(int i=1;i<=gp;i++)
		{
			for(int j=i;j<=9;j++)
			{
				if(chk(n-j,gp-i))
				{
					ans=ans*10+j;
					n-=j;
					break;
				}
			}
		}
		printf("%lld\n",ans);
	}
	return 0;
}