TSHOW1 - Amusing numbers

Amusing numbers are numbers consisting only of digits 5 and 6. Given an integer k , display the k-th amusing number.

Input

FIrst line consists of integer N representing number of test cases

Next N lines consist of N integers (1 <= k <= 10^15)

Output

N lines each displaying corresponding k-th amusing number

Example

Input:
2
1
5

Output:
5
65

Added by:Pandian
Date:2012-04-10
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:AOL code contest

hide comments
2024-07-06 07:38:48
nice!
2020-05-27 09:45:39
bit manipulation would do!
2019-10-15 12:15:11 vikash
Submitted the same solution in Java and scala.
Scala shows time limit exceeded. Jave runs fine.
In scala only code to take input also exceeds time.

2019-07-13 06:50:53
I did it using binary tree..
Create a binary tree, with root node * (empty)..
5 is left child and 6 is right child..
for instance n=11
record the parent and path of 11 i.e. 5, Left (parent = floor(n-1)/2, path = L if int(parent)==parent else R)
push the path to the stack and keep find parents.
now n=5
parent, path = 2, L
now n =2
parent = 0, R
generate the num..
later generate the num using the stack of recorded path

Last edit: 2019-07-13 06:52:35
2019-05-15 00:03:26
Excellent question, brilliant concept !
2018-10-30 08:28:27
nice go
2018-10-27 20:04:38
think binary!!!
2018-06-29 17:56:24
Hints
#1. https://www.spoj.com/problems/SILVER/
#2. Knowing the no. of digits in Kth amusing no. will help
#3. We just have 2 numbers 5/6. We have to form a number system using these two numbers. The only catch is in this number system 0/00/000/0000.......... will also hold values

Last edit: 2018-06-29 21:05:38
2017-09-29 07:52:52
AC in one go!!! Very good question!
2017-07-16 13:15:39 vi1
Easy, but fun :)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.