using namespace std;

#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>

#define EPS 1e-11
#define inf ( 1LL << 31 ) - 1
#define LL long long

#define _rep( i, a, b, x ) for( __typeof(b) i = ( a ); i <= ( b ); i += x )
#define rep( i, n ) _rep( i, 0, n - 1, 1 )
#define rrep( i, a, b ) for( __typeof(b) i = ( a ); i >= ( b ); --i )
#define xrep( i, a, b ) _rep( i, a, b, 1 )

#define abs(x) (((x)< 0) ? (-(x)) : (x))
#define all(x) (x).begin(), (x).end()
#define ms(x, a) memset((x), (a), sizeof(x))
#define mp make_pair
#define pb push_back
#define sz(k) (int)(k).size()

typedef vector <int> vi;
const LL MOD = 1000007;

int n;

LL memo[50][70][70][70];
int tcase[50][70][70][70];
int ncase;

int LCM[70][70];

LL solve(int pos, int nmod, int lcm, int clcm)
{
    if (pos == n) return (nmod == 0 && lcm == clcm);
    LL &ret = memo[pos][nmod][lcm][clcm];
    if (tcase[pos][nmod][lcm][clcm] == ncase) return ret;
    tcase[pos][nmod][lcm][clcm] = ncase;
    ret = 0;
    xrep(i,1,6) if (lcm % i == 0)
    {
        ret += solve(pos + 1, (nmod * 10 + i) % lcm, lcm, LCM[clcm][i]);
        ret %= MOD;
    }
    return ret;
}

int main()
{
    #ifdef Local
        freopen("/home/wasi/Desktop/input.txt", "r", stdin);
    #endif
    xrep(i,1,65) xrep(j,1,65) LCM[i][j] = (i*j) / (__gcd(i, j));
    vi dig, lcms;
    set<int> L;
    xrep(i,1,6) dig.pb(i);
    rep(i,(1<<6))
    {
        int l = 1;
        rep(j,6) if (i & (1<<j))
            l = LCM[l][dig[j]];
        L.insert(l);
    }
    lcms = vi(all(L));



    int tc;
    scanf("%d", &tc);

    while (tc--)
    {
        ncase++;
        scanf("%d", &n);
        LL ans = 0;
        rep(i,sz(lcms))
        {
            ans += solve(0, 0, lcms[i], 1);
            ans %= MOD;
        }
        printf("%lld\n", ans);
    }


    return 0;
}