Under construction

Still being built. Things may change

Super Lucky Palindromes

Time limit1sMemory limit1024 MB

Summary
Given k, find the k-th smallest palindrome whose digits are all 4 or 7, whose digit count is lucky, and whose count of 4s or 7s is lucky.
Level

Medium6 of 10

Topics
Combinatorics, Math, Implementation
Solved
No attempts yet

Problem

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

A super lucky number satisfies all of the following conditions.

  • It is a lucky number.
  • Its number of digits is a lucky number.
  • The count of 4s or the count of 7s in it is a lucky number (both counts may be 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 k, print the k-th smallest super lucky palindrome.

Input

The first line contains a positive integer n, the number of queries. Each of the next n lines contains a single integer k (1≤k≤10181 \le k \le 10^{18}).

Output

For each query, print 'Query #d: ' followed by the k-th smallest super lucky palindrome, where d is the query number starting from 1.

Examples1

  1. Example 1

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