Compute the Combination

Let P = C(N,0) - C(N,1) + C(N,2) - C(N,3) + ... + C(N,N); where C(n,r) is "n choose r".

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

Input

Input starts with an integer T (1 <= T <= 1000000), denoting the number of test cases. Each test case contains an integer N (0 <= N <= 1000000).

Output

For each test case, print the value of P.

Sample

Input	Output
1 4	0

This problem was authored for CodeMask Championship 2016 and is being hosted on Toph per organizer’s request.