Joey never liked Maths, because he doesn't like counting. Ten digits and base 10 always makes him suffer while counting. So he wondered what if there were only three numbers 2,3 and 4. Then counting would have been 2,3,4,22,23,24.... and so on.

Now it's Chandler, who is totally fed up with joey's wonderings! Just to stop him from blabbering all this, he asks, "Joey, can you tell me what would be Kth number in your counting, taking 2 as the first?". And Of course, Joey can't answers this! but Can you?

You have to tell what would be the Kth number when only digits you can use are 2,3 and 4.

Input:

          First line containing T, the number of test cases.

          Then T lines, each with K

Output:

          Print the Kth number made-up of digits 2,3 and 4, in a new line.

Constraints:

          1 <= T <= 100000

          1<= K <= 10^15