A. A Matchsticks Problem
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You have $$$n$$$ matchsticks.Your task is to combine them to make a number.

Here're some restrictions:

  1. Each and every digit must be put together exactly as shown in the image above.
  2. The $$$n$$$ marchsticks must all be used up.
  3. There may be leading zeros in the number.

Find the least possible number.

Input

The first line of input will contain a single integer $$$t(1 \leq t \leq 1000)$$$, denoting the number of test cases.

Each test case consists of a line of input.The only line of each test case contains an integer $$$n(2 \leq n \leq 1000)$$$.

Output

For each test case, output on a new line — the the smallest number you can get.

Example
Input
3
4
8
60
Output
4
01
0000000000