# Appreciation

/*
 * Problem :: 2780 / 비밀번호
 *
 * Kind :: Dynamic Programming
 *
 * Insight
 * - 비밀번호에서 인접한 수는 실제 위 기계의 번호에서도 인접해야 한다
 *   + dp[i][j] = 길이 i 이고 숫자 j 로 끝나는 비밀번호의 개수라고 한다면,
 *     위를 구하기 위해서는 j 와 인접한 숫자들로 끝나는 길이 i-1 로 끝나는 비밀번호의 개수를
 *     모두 더해주면 된다
 */

# Code

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

#define endl '\n'

// Set up : Global Variables
/* None */

// Set up : Functions Declaration
/* None */


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Process
    vector<int> A[10]; /* 각 숫자의 인접한 숫자들이 저장된 Vector 배열 */
    A[1] = {2, 4};
    A[2] = {1, 3, 5};
    A[3] = {2, 6};
    A[4] = {1, 5, 7};
    A[5] = {2, 4, 6, 8};
    A[6] = {3, 5, 9};
    A[7] = {4, 8, 0};
    A[8] = {5, 7, 9};
    A[9] = {6, 8};
    A[0] = {7};

    int dp[1000+1][10]; /* dp[i][j] = 길이 i 이며 숫자 j 로 끝나는 비밀번호의 개수 */
    memset(dp, 0, sizeof(dp));
    for (int i=0; i<10; i++) {
        dp[1][i] = 1; /* 초기화 <= 길이 1 이며 숫자 j 로 끝나는 비밀번호의 개수는 모두 1임 */
    }
    for (int i=2; i<=1000; i++) {
        for (int j=0; j<10; j++) {
            for (int a : A[j]) { /* 숫자 j 에 인접한 숫자들을 a 라는 변수로 하나씩 뽑아냄 */
                dp[i][j] += dp[i-1][a];
                dp[i][j] %= 1'234'567;
            }
        }
    }

    // Set up : Input
    int T; cin >> T;

    while (T--) {
        int N; cin >> N;

        // Control : Output
        int ans = 0;
        for (int i=0; i<10; i++) { /* N 자리 비밀번호의 개수는 dp[N][0~9] 의 합 */
            ans += dp[N][i];
            ans %= 1'234'567;
        } cout << ans << endl;
    }
}

// Helper Functions
/* None */