Migrated from Lutece 1861 Foxtrot

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Doctor Foxtrot has $N$ kinds of potion, but just one kind of them can kill rats. Doctor Foxtrot has forgot which one is harmful to rats. The rats is scarce, so Doctor Foxtrot wants you to help him find the only kind of potion with minimum number of rats.

All rats drink potion on the first day, and the result is on the second day. Any rat drunk harmful potion will die on the second day. One rat can drink more than one kind of potion.

Input

The first line is an integer $T$($1 \leq T \leq 62$), which indicates the number of testcases.

For each testcase:

The one line of the input contains one integer $N$ ($1 \leq N \leq 10^9$), denoting the number of kinds of potion.

Output

For each testcase, in the only line of output print the minimum number of rats needed.

Samples

1
2

1

1
3

2

Resources

The 16th UESTC Programming Contest Preliminary