Problem Description

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 one integer $N(1 \leq N \leq 10^9)$.

Output

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

2
1
6

2
4