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<stdio.h>
int main()
{
    int o;
    scanf("%d", &o);
    for (int p = 0; p < o;p++)
    {
        int n;
        scanf("%d", &n);
        if(n>45)
            printf("%d\n", -1);
        else if(n>0&&n<=9)
        {
            printf("%d\n", n);
        }
        else if(n>9&&n<=17)
        {
            for (int i = 1; i <= 8;i++)
            {
                if(i+9==n)
                {
                    printf("%d%d\n", i, 9);
                    break;
                }
            }
        }
        else if(n>17&&n<=24)
        {
            for (int i = 1; i <= 7;i++)
            {
                if(i+17==n)
                {
                    printf("%d%d%d\n", i, 8, 9);
                }
            }
        }
        else if(n>24&&n<=30)
        {
            for (int i = 1; i <= 6;i++)
            {
                if(i+24==n)
                {
                    printf("%d%d%d%d\n", i,7, 8, 9);
                }
            }
        }
        else if(n>30&&n<=35)
        {
            for (int i = 1; i <= 5;i++)
            {
                if(i+30==n)
                {
                    printf("%d%d%d%d%d\n", i,6,7, 8, 9);
                }
            }
        }
        else if(n>35&&n<=39)
        {
            for (int i = 1; i <= 4;i++)
            {
                if(i+35==n)
                {
                    printf("%d%d%d%d%d%d\n", i,5,6,7, 8, 9);
                }
            }
        }
        else if(n>39&&n<=42)
        {
            for (int i = 1; i <= 3;i++)
            {
                if(i+39==n)
                {
                    printf("%d%d%d%d%d%d%d\n", i,4,5,6,7, 8, 9);
                }
            }
        }
        else if(n>42&&n<=44)
        {
            for (int i = 1; i <= 2;i++)
            {
                if(i+42==n)
                {
                    printf("%d%d%d%d%d%d%d%d\n", i,3,4,5,6,7, 8, 9);
                }
            }
        }
        else if(n==45)
            printf("%d%d%d%d%d%d%d%d%d\n", 1, 2, 3, 4, 5, 6, 7, 8, 9);
    }
}