Time Limit: 1000 MS    Memory Limit: 65536 K   

Description


There is a function F(n)=3*F(n-1)*2F(n-2)+1.Now,you know F(0)=1,F(1)=3.
Give you a number n, write a program to calculate F(n).
F(n) may quite large, you should mod 20121223.

Input


There are several test cases. The first line is the number of test cases.
For each test case,there is only one number n(0<=n<=1000).

Output


For each input n,print the answer F(n) in a line.

Sample Input


3
0
1
2

Sample Output


1
3
12


Author


citycan_1991