Last time you helped Rancho getting kisses from Pihu. This time Pihu needs your help in determining the number of, different ways of kissing.

Actually the story goes this way.

Rancho will fix a certain number of days, say N (N <= 10^18). Now Pihu as usual, will kiss Rancho each day, but this time there will be rules for kissing. Rules go below:-

Suppose for a certain number of days N, Pihu needs to learn P different ways of kissing. She can kiss Rancho on every day with any number of kisses (of course less than or equal P), but all the kisses should be different from each other. Also to keep “Kissing of each day” unique, between every pair of days, say day i and day j (i not equal j), day i must have at-least one type of kiss that day j does not have and day j must have at-least one type of kiss that day i does not have. (Refer explanation below)

Help Pihu, determine the minimum number of different ways/types of kissing for N days – call the minimum number as P.

Explanation:

Suppose on day i, Pihu kisses Rancho with a set S_i – (k₁, k₂, k₃ ... k_m : k₁≠k₂≠k₃≠ ... ≠k_m) kisses and on day j with a set S_j – (k₁, k₂, k₃ ... k_l : k₁≠k₂≠k₃≠ ... ≠k_l), then there should be at-least one k_i in set S_i that is not in set S_j and there should be at-least one k_j in set S_j that is not in set S_i. Thus you can consider P as the size of the superset of S₁,S₂,S₃ ... S_N.

Input

The first line of input consists of the number of test cases T (T <= 100000).

Next follows T lines, with each line consisting of one number N – the number of days (1 <= N <= 10^18).

Output

For each test case print the minimum number of different ways of kissing – P on separate lines.

Example

Input:
3
1
2
3

Output:
1
2
3