Keypad Passwords

Seokwon installed a numeric password keypad on his front door. The buttons are arranged as follows.

1 2 3
4 5 6
7 8 9
0

Two buttons are adjacent when they touch vertically or horizontally. Therefore, 0 is adjacent only to 7.

A password of length N is made by pressing buttons from this keypad in order. Every pair of consecutive digits in the password must also be adjacent on the keypad. For example, 15 cannot be made because 1 and 5 are not adjacent, but 1-2-3-6 can be made because every consecutive pair is adjacent.

Juhui wants to know the total number of possible passwords of length N. The first digit may be 0.

The first line contains the number of test cases, T. Then, for each test case, one line contains the password length N.

1 <= N <= 1000

For each test case, print the number of passwords satisfying the conditions on its own line.

Because the number can be very large, print the remainder after dividing the answer by 1,234,567.