ATWO - The power of two

no tags 

World is a funny place, one moment you are walking around the street eating some chicken and the other you are wondering: what numbers are a power of 2? not only that, you also want to know,  given a number that isn't a power of 2, the closest increasing power of 2, that means for example that if you get: 5, you will show 5 8, because 8 is the closest increasing power of 2 from 5.

Input

first line will have a T (1<=T<=10000) the next T lines will contain an integer (which we do not ensure that fits on 32-bits, but maybe it does.)

Output

If the number is a power of 2, just print it. If it is not a power of two, you will print the number and after that print the closest increasing power of 2.

Example

Input:
4
0
1
2
3 Output: 0 1
1
2
3 4

hide comments
Mostafa 36a2: 2012-11-19 20:48:44

@Rodolfo Miquilarena
what is the maximum integer in input?
can it be more than 2^64 ??

Edit: no, there is no need to use big int on this problem, you are just doing a wrong approach ;)
Edit: OK :)),i'm happy with the 2 points but it's totorial any way...good by my points :D
Edit: yep it will be xD

Last edit: 2012-11-19 21:02:06

Added by:Rocker3011
Date:2012-11-19
Time limit:0.209s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:own problem