#include <bits/stdc++.h>

using namespace std;
std::mt19937_64 rnd(42);

//#define int long long
#define ld long double
#define ull unsigned long long
#define all(x) x.begin(), x.end()

const int SMALL_INF = 1000000007; //9
const long long BIG_INF = 2000000000000000000; //18
const int MOD = 998244353;
const long long ONE = 1;

void Ans(int x) {
    if (x == 0) {
        cout << "NO";
    }
    else {
        cout << "YES";
    }
    cout << endl;
}

int take(long long x, int n) {
    return (x >> n) & 1;
}

int mul(long long a, long long b) {
    return (a * b) % SMALL_INF;
}

int sum(int a, int b) {
    if(a + b >= SMALL_INF) {
        return a + b - SMALL_INF;
    }
    return a + b;
}

const int sz = 33;

array<array<int, sz>, sz>mul_matrix(array<array<int, sz>, sz>&a, array<array<int, sz>, sz>&b) {
    array<array<int, sz>, sz>ans{};

    for(int i = 0; i < a.size(); i++) {
        for(int j = 0; j < b[0].size(); j++) {
            for(int k = 0; k < b.size(); k++) {
                ans[i][j] = sum(ans[i][j], mul(a[i][k], b[k][j]));
            }
        }
    }

    return ans;
}

array<int, sz>mul_vec_matrix(array<int, sz>&a, array<array<int, sz>, sz>&b) {
    array<int, sz>ans{};

    for(int i = 0; i < b[0].size(); i++) {
        for(int j = 0; j < b.size(); j++) {
            ans[i] = sum(ans[i], mul(a[j], b[j][i]));
        }
    }

    return ans;
}

const int mx = 60, block_sz = 4, num_blocks = 15;

array<int, sz>start;
array<array<int, sz>, sz>v, one_matrix;
array<array<array<int, sz>, sz>, mx>pw;
array<array<array<array<int, sz>, sz>, ONE << block_sz>, num_blocks>blocks;

array<int, sz> bin(long long p) {
    array<int, sz>ans = start;

    for(int i = 0; i < num_blocks; i++) {
        int mask = ((p >> (i * block_sz)) & ((ONE << block_sz) - 1));
        ans = mul_vec_matrix(ans, blocks[i][mask]);
    }

    return ans;
}

int calc_ans(array<int, sz>&x) {
    int ans = 0;
    for(int i = 0; i < x.size(); i++) {
        ans = sum(ans, x[i]);
    }

    return ans;
}

int gcd(int a, int b) {
    if(a == 0 && b == 0) {
        return 0;
    }

    while(b) {
        int k = a;
        a = b;
        b = k % b;
    }

    return a;
}

void solve() {
    long long n;
    cin >> n;

    auto res = bin(n - 2);

    cout << calc_ans(res);
}

void testing() {
    int cnt = 0;

    while (true) {
        if (cnt == -1) {
            int ab = 0;
            ab--;
        }

        if (cnt % 10000 == 0) {
            cout << cnt << endl;
        }

        cout << cnt << endl;
    }
}

void precalc() {
    for(int i = 0; i < sz; i++) {
        one_matrix[i][i] = 1;
    }

    vector<pair<int, int>>pr;
    pr.push_back({0, 0});
    map<pair<int, int>, int>mp;

    for(int d = 0; d < 10; d++){
        for(int g = 1; g < 10; g++) {
            if(d % g == 0) {
                pr.push_back({d, g});
                mp[{d, g}] = pr.size() - 1;
            }
        }
    }

    for(int i = 0; i < sz; i++) {
        for(int next_digit = 0; next_digit < 10; next_digit++) {
            int d = pr[i].first;
            int g = pr[i].second;

            int cur_g = gcd(d, next_digit);
            int ind = mp[{next_digit, cur_g}];

            if(gcd(d, next_digit) != g) {
                v[i][ind] = 1;
            }
        }
    }

    /*for(int d1 = 0; d1 < 10; d1++) {
        for(int d2 = 0; d2 < 10; d2++) {
            for(int d3 = 0; d3 < 10; d3++) {
                if(gcd(d1, d2) == gcd(d2, d3)) {
                    continue;
                }

                v[d2][d3]++;
            }
        }
    }*/

    for(int i = 1; i < 10; i++) {
        for(int j = 0; j < 10; j++) {
            start[mp[{j, gcd(i, j)}]]++;
        }
    }

    auto cp = v;

    for(int i = 0; i < mx; i++) {
        pw[i] = cp;
        cp = mul_matrix(cp, cp);
    }

    for(int i = 0; i < num_blocks; i++) {
        for(int mask = 0; mask < (ONE << block_sz); mask++) {
            blocks[i][mask] = one_matrix;

            for(int b = 0; b < block_sz; b++) {
                if(take(mask, b) == 0) {
                    continue;
                }

                blocks[i][mask] = mul_matrix(blocks[i][mask], pw[i * block_sz + b]);
            }
        }
    }
}

signed main() {
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);

    //testing();

    precalc();

    int test = 1;
    std::cin >> test;
    while (test--) {
        solve();

        std::cout << "\n";
        //std::cout << std::endl;
        //std::cout << std::endl;
    }

    return 0;
}