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