비밀번호 개수

석원이는 현관문에 숫자 버튼으로 된 비밀번호 기계를 설치했다. 버튼은 다음과 같이 놓여 있다.

1 2 3
4 5 6
7 8 9
0

두 버튼이 위아래 또는 양옆으로 맞닿아 있을 때 인접하다고 한다. 따라서 0은 7과만 인접한다.

길이가 N인 비밀번호는 위 버튼 중 하나를 차례로 눌러 만든다. 비밀번호에서 서로 이웃한 두 숫자는 기계에서도 반드시 인접해야 한다. 예를 들어 1과 5는 인접하지 않으므로 15는 만들 수 없지만, 1-2-3-6은 모든 이웃한 숫자 쌍이 인접하므로 만들 수 있다.

주희는 길이가 N인 비밀번호를 만들 수 있는 전체 경우의 수를 알고 싶다. 첫 숫자는 0도 될 수 있다.

첫 번째 줄에 테스트 케이스의 수 T가 주어진다. 이어서 각 테스트 케이스마다 한 줄에 비밀번호의 길이 N이 주어진다.

1 <= N <= 1000

각 테스트 케이스마다 조건을 만족하는 비밀번호의 개수를 한 줄에 하나씩 출력한다.

수가 매우 커질 수 있으므로, 답을 1,234,567로 나눈 나머지를 출력한다.