NBIN - New Binary

One day Chandrima decided to make a list of all numbers starting from 1 in binary format, the list would be like 1, 10, 11, 100, ... and so on. Now she get bored of this list and decide to remove any pattern having at least two consecutive ones and prepare a new list. The new list will be like 1, 10, 100, 101, ... and so on. She then thought if a number n is given to her can she find the nth member of the new list. After trying for some time she comes to you for help. Can you help her by writing a program for her that coud do the specified task

Input

The first line contains T (<= 1000) test cases. The next T lines each contain one integer N (<= 10^15) for which you need to find the Nth member of the list.

Output

Output T lines each containing the required answer.

Example

Input:
3
1
2
3

Output:
1
10
100

Added by:Abhra
Date:2014-04-16
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2014-07-21 11:09:04 venky
@Kanish_The_Vista
I think the answer for 13 is
100000
2014-04-24 13:57:08 Kanish_The_Vista
@ABHRA
what is the o/p of 13

Last edit: 2014-07-21 11:09:15
2014-04-18 04:34:09 sankar
Enjoyed solving this :)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.