Color the blocks

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≤T≤105).

For every test case,the first line has one integer N(1≤N≤109).

Output

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

Sample Input

2
1
6

Sample Output

2
4

题目大意：

给定一个NN的网格，你可以把一格涂成黑或者白两种颜色，但对于每一个位置(x, y)，(x−3,y),(x−1,y+2),(x+1,y+2),(x+3,y)四个位置不能和它为同一个颜色，给定任意的N，问NN的网格有多少种可能的涂法。

题解：

通过观察我们可以发现，一个格子控制的其他四个格子的位置都在同列或者往后两列的位置。

我们把相关联的格子用绿色表示：

可以发现奇数列和偶数列是不会互相影响的，而奇数列只会有两种可能，偶数列也会有两种可能，所以当N大于某个数时都只有2 * 2 = 4种可能。

当N = 1时，答案为1；
当N = 2时，四个格子都互不影响，答案是2 * 2 * 2 * 2 = 16；
当N = 3时：

绿色两种可能，黄色两种可能，白色三个格子互不影响，
答案为2 * 2 * (2 * 2 * 2）= 32;

当N >= 4时，答案就是恒定的4了。

AC代码:

#include <iostream>
using namespace std;
int main() {
	ios::sync_with_stdio(false);
	int t;
	cin >> t;
	while (t --) {
		int n;
		cin >> n;
		if (n == 1) cout << "2\n";
		else if (n == 2) cout << "16\n";
		else if (n == 3) cout << "32\n";
		else cout << "4\n";
	}
	return 0;
}