Let P = C(N, 0) - C(N, 1) + C(N, 2) - C(N, 3) + ... C(N, N)

You are given N. You have to find the value of P.

Input

Input starts with an integer T, denoting the number of test cases. Each test case contains an integer N.

Constraints

0 <= N <= 1000000

1 <= T <= 1000000

Output

For each test case, print the value of P.

Example

Input:
1
4

Output:
0

Note: use faster i/o method.

Problem Setter: Md Abdul Alim, Dept. of Computer Science, Bangladesh University of Business & Technology