KZGD - Good Sequence

It is good to hav an auspicious start to any event.The kruzade OPC team felt that online coding event should
also have an auspicious start.As a mark of auspiciousness, we define good sequence as follows:
A good number is defined as a non-negative number that has an odd number of 1s in its binary
expansion(that is when the decimal number is converted to base 2).
for eg.
1=1  num of 1s in binary equiv=1(odd) so,1 is a good number
2=10 num of 1s in binary equiv=1(odd) so,2 is a good number
3=11 num of 1s in binary equiv=2(even) so,3 is not a good number

The good sequence is the collection of good numbers.
The good sequence goes like this:
1,2,4,7,8,11,13,14,16,19...

You have been hired to find out the nth good number in the sequence.

Input

First line contains an integer T, representing the number of test-cases. Then T lines
follow each containing one integer n, 1 <= n <= 500.

Output

For each test case output on a line the nth good number in the sequence.

Example

Input:
3
10
5
20 Output: 19
8
38

Added by:balaji
Date:2009-09-28
Time limit:1.519s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL
Resource:kruzade 09 main

hide comments
2009-11-11 15:36:37 ckclark
Can this problem remove the trailing cr?
I get NZEC using function "input" in python.
2009-09-28 11:47:55 abhijith reddy d
I guess this will again be moved to the tutorial section :P
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.