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