CTPLUCKY - Super Lucky Palindromes

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

Added by:Mew.
Date:2014-09-16
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM32-GCC ASM64 MAWK BC C-CLANG NCSHARP CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JS-MONKEY JULIA KTLN NIM OBJC OBJC-CLANG OCT PICO PROLOG PYPY PYPY3 R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET
Resource:LPC UCF 2014

hide comments
2019-05-06 16:07:22
Hello, sorry to say that here, I'm very new on this website and I don't understand how everything works.
I think I did solve the problem correctly because I have the same results with the exemple above but I keep having errors when I submit the solution.
How can I know If my algorithm is wrong or if my submitting form is wrong ?
A sample : <gone>
In either way, I really enjoyed solving it. Thanks for the problem :)

Edit : Ok, I followed the tutorial and I was using a main() function as the tutorial did but I'm using python and not C++ (so I don't need that)
Sorry for the inconveniance

Last edit: 2022-06-10 23:10:21
2015-07-29 23:33:37 Scape
Nice problem. Had fun solving it.
2014-09-17 15:08:32 Mew.
they're both super lucky numbers
2014-09-17 14:31:50 Ehor Nechiporenko
Why 7474747 and 7777777 are not super lucky numbers?! In both number of 7'th is a lucky number.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.