You are given a special set of pure numbers.

 A pure number has the following properties:

1. It comprises only 4 and 5.
2. It is a palindrome number.
3. The number of digits in a pure number is even.

For example, 4444,5445,44 are the pure numbers while 12,444,4545 are not. You have to generate a list of pure numbers in an ascending order. So, purenumber[1] < purenumber[2].

The first few elements in the list are as follows: 44,55,4444,....

You will be given an integer $N$ and you have to find $N^{th}$ pure number from the generated list.

Example

Consider N = 2. You must determine the $N^{th}$ pure number from the generated list.

The $2^{nd}$ pure number in the list is 55.

Therefore the answer is 55.

Function description

Complete the solve function provided in the editor. This function takes the following 1 parameter and returns the  $N^{th}$ pure number from the generated list.

• N: Represent the Nth pure number that needs to be found

Input format

Note: This is the input format that you must use to provide custom input (available above the Compile and Test button).

• First line: $T$ denoting the number of test cases
• Next $T$  lines: A number $N$ 

Output format

• Print the $N^{th}$ pure number.

Constraints
$1 \le T \le 10^6$
$1 \le N \le 10^6$

Code snippets (also called starter code/boilerplate code)

This question has code snippets for C, CPP, Java, and Python.