Description

Sperner is an industrious boy excelling at solving mathematical problems. This time he encountered a tough problem concerning about sets, hence your help will be of great value.

Given a set A with a size n, and you can create a set B whose elements are subsets of A. But you should guarantee that the element s of B don’t belong to each other, which displays the constraint that if u and v belong to B, then u is not a subset of v and vice versa(note that B is a set formed by subsets of A).

Here comes the real problem, what is the maximum size of B?

Input

The first line of input contains a number T (1<T<50), which is the number of test cases. Each of the following T lines contains one integer n (1<=n<=50), which is the size of A.

Output

For each test case, print a line the maximum size of B corresponding to n, the size of A.

Sample

Input

2
1
2

Output

1
2

Source: Limitfan