Lucky numbers are positive integers composed only of the digits ‘4’ and ‘7’. For example, 47477 and 777 are lucky numbers while 457 and 1232 are not.

Super lucky numbers have the following additional properties:

• They are a lucky number themselves.
• Number of digits in them is a lucky number.
• The number of ‘4’s or the number of ‘7’s in them is a lucky number (or both counts are lucky numbers).

A palindrome is an integer that reads the same forwards and backwards. For example, 547745 and 343 are palindromes while 74 and 12345 are not. A super lucky palindrome is a positive integer that is both a super lucky number and a palindrome.

Given a number k, print the k-th smallest super lucky palindrome.

Input

The first input line contains a positive integer, n, indicating the quantity of numbers to check.

Each of the next n lines contains a single integer, k (1 ≤ k ≤ 10^18).

Output

For each query, first output the heading “Query #d: ”, where d is the query number, starting with 1.

Then, for the value k given in the query, print the k-th smallest super lucky palindrome.

Follow the format illustrated in Sample Output.

Example

Input:
5
1
2
3
5
100
Output:
Query #1: 4444
Query #2: 7777
Query #3: 4444444
Query #4: 4747474
Query #5: 44444444744744444444444444444444744744444444