J. Color the blocks
time limit per test
1 second
memory limit per test
64 megabytes
input
standard input
output
standard output

Given you an $$$N*N$$$ grid graph,you can color any block black or white,but you have to meet the condition:

For each block $$$(x,y)$$$,it can't be the same color as $$$(x-3,y),(x-1,y+2),(x+1,y+2),(x+3,y)$$$.

You need to calculate the total number of options for coloring the $$$N*N$$$ grid graph.

Input

There are $$$T$$$ test cases in this problem.

The first line has one integer $$$T(1 \leq T \leq 10^5)$$$.

For every test case,the first line has $$$1$$$ integer $$$N(1 \leq N \leq 10^9)$$$.

Output

For every test case, output the answer in a line.

Example
Input
2
1
6
Output
2
4