Permutations and Combination is Soumyadeep's favourite topic on mathematics. Today, his teacher has asked him a rather curious question.

Given any $N * N$ matrix, in how many different ways can you fill it with only 0 & 1 such that every $2 * 2$ matrix inside the given $N * N$ matrix will have exactly two 0 & two 1.

Being the teacher's favourite student, it has become a matter of prestige for him to solve the puzzle. Help Soumyadeep solve this problem.

Input Format
The first line contains a single integer, containing the number of testcases, T. Each test case contains 1 line, N.

Output Format
The output consists of T lines. Each line consists of 1 integer, that is, the number of possible combinations.

Constraints
$1 \le T \le 10^6$
$2 \le N \le 30$