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 <algorithm>
#include <iostream>
#include <cstdlib>
#include <iomanip>
#include <utility> 
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <map>
#include <set>

#define ll long long
#define endl '\n'

using namespace std;

void solve(int x, int n) {
	if (n <= 0) return;
	if (x-n >=0) {
		solve(x-n, n-1);
		cout << n;
	} else {
		solve(x, n-1);
	}
}

int main() { 
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  	srand(time(0));

  	int t;
  	cin >> t;
  	while (t--) {
  		int x;
  		cin >> x;
  		if (x > 45) cout << -1 << endl;
  		else if (x <= 9) cout << x << endl;
  		else {
  			solve(x, 9);
  			cout << endl;
  		}
  	}

	return 0;
}