PIHU2 - Love Story 2

no tags 

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 Si – (k1, k2, k3 ... km : k1≠k2≠k3≠ ... ≠km) kisses and on day j with a set Sj – (k1, k2, k3 ... kl : k1≠k2≠k3≠ ... ≠kl), then there should be at-least one ki in set Si that is not in set Sj and there should be at-least one kj in set Sj that is not in set Si. Thus you can consider P as the size of the superset of S1,S2,S3 ... SN.

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


Added by:sobriquet
Date:2014-06-17
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU
Resource:My own problem