// Arup Guha
// 9/7/2013
// Solution to UCF JV Practice Problem C: Tiling

import java.util.*;

public class c {

	final public static int MAX = 500;
	final public static int MOD = 10007;

	public static void main(String[] args) {

		// Pre-compute answers: to tile 2xn, we can place a vertical tile at the end and tile 2x(n-1)
		// or we can place a square and tile 2x(n-2) or two horizontal tiles and tile 2x(n-2)
		// So, the recurrence relation is f(n) = f(n-1) + 2*f(n-2)
		int[] ans = new int[MAX+1];
		ans[1] = 1;
		ans[2] = 3;
		for (int i=3; i<=MAX; i++)
			ans[i] = (ans[i-1] + 2*ans[i-2])%MOD;

		Scanner stdin = new Scanner(System.in);
		int numCases = stdin.nextInt();

		// Just answer every case.
		for (int loop=0; loop<numCases; loop++) {
			int n = stdin.nextInt();
			System.out.println(ans[n]);
		}
	}
}