Shortening codes

For gven integer n print next power of 2 greater than n.

Input

The first line of the standard input contains one integer t (t<10001) which is the number of test cases.

In each of the next t lines there is an integer n (0<=n<=10^9).

Output

For each test, print the next power of 2 greater than n.

Example

Input:
5
5
4
10
16
100
Output:
8
8
16
32
128