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 <bits/stdc++.h>
using namespace std;

int tt;
int x;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> tt;
    while (tt--) {
        cin>>x;
        if(x>45){
            cout<<"-1\n";
            continue;
        }
        int ans = 0x3f3f3f3f;
        for(int k = 0; k<(1<<10); k++){
            // memset(vis, 0, sizeof(vis));
            int s = 0, sum = 0;
            for(int j = 0; j<10; j++){
                if(k>>j&1){
                    s = s*10+j;
                    sum+=j;
                    // vis[j] = 1;
                }
            }
            if(sum==x){
                ans = min(s, ans);
            }
        }
        cout<<ans<<'\n';
    }

    return 0;
}