#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
int a[] = {30,19,13,11};
int b[15];
 
int dp[11][2][2][31][20][14][12];
int mod = 1e9+7;
int INF= 1e9+1;
 
ll get(int x1, int x2, int x3, int x4) {
    ll res = 1;
    while(x1-->0) {
        res *=2;
        if(res>INF) return res;
    }
    while(x2-->0) {
        res *=3;
        if(res>INF) return res;
    }
    while(x3-->0) {
        res *=5;
        if(res>INF) return res;
    }
    while(x4-->0) {
        res*=7;
        if(res>INF) return res;
    }
    return res;
}
 
int go(int p, bool z, bool g, int a2, int a3, int a5,int a7) {
    if(p==-1) return z && (a2==0) && (a3==0) && (a5==0)&& (a7==0);
    int &res = dp[p][z][g][a2][a3][a5][a7];
    if(res>=0) return res;
    res = 0;
    if(!z) res = go(p-1,z,g || (0<b[p]),a2,a3,a5,a7);
    for(int i=1;i<=9; i++) {
        if(g ||(i<=b[p])) 
        {
            int b2 = a2,b3=a3, b5=a5, b7=a7;
            if(i%8==0) b2-=3;
            else if(i%4==0) b2-=2;
                else if(i%2==0) b2--;
                if(i%9==0) b3-=2;
                else if(i%3==0) b3--;
                if(i%5==0) b5--;
                if(i%7==0) b7--;
                if(b2>=0 && b3>=0 && b5>=0 && b7>=0) {
        res+=go(p-1,1,g||(i<b[p]),b2,b3,b5,b7);
            }
 
        }
    }
    return res;
}
 
int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */  
    int t;
    cin>>t;
    while(t-->0) {
        memset(dp,-1,sizeof(dp));
    int ret =0;
    int n;
    cin>>n;
    for(int i=0; i<=11;i++) {
        b[i]= n%10;
        n/=10;
    }
    for(int i=0;i<=a[0]; i++) {
        for(int j=0;j<=a[1]; j++) {
            for(int k=0; k<=a[2];k++) {
                for(int l=0;l<=a[3]; l++){ 
                    ll res = get(i,j,k,l);
                    if(res>=INF)continue;
                    int cur = res;
                    int ans = go(10,0,0,i,j,k,l);
                    int phi = cur, div = 1;
                    for(int m=2;m*m<=cur; m++) {
                        if(cur%m==0) {
                            int tot = 0;
                            while(cur%m==0) {
                                cur/=m;
                                tot++;
                            }
                            phi /=m;
                            phi*=(m-1);
                            div *= (tot+1);
                        }
                    }
                    if(cur>1) {
                        phi /=cur;
                        phi *= (cur-1);
                        div *= 2;
                    }
                    ret=(ret+((ans*1LL*phi)%mod)*1LL*div)%mod;
                }
            }
        }
    }
    cout<<ret<<endl;
    }
    return 0;
}

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgojZGVmaW5lIGxsIGxvbmcgbG9uZwppbnQgYVtdID0gezMwLDE5LDEzLDExfTsKaW50IGJbMTVdOwoKaW50IGRwWzExXVsyXVsyXVszMV1bMjBdWzE0XVsxMl07CmludCBtb2QgPSAxZTkrNzsKaW50IElORj0gMWU5KzE7CgpsbCBnZXQoaW50IHgxLCBpbnQgeDIsIGludCB4MywgaW50IHg0KSB7CiAgICBsbCByZXMgPSAxOwogICAgd2hpbGUoeDEtLT4wKSB7CiAgICAgICAgcmVzICo9MjsKICAgICAgICBpZihyZXM+SU5GKSByZXR1cm4gcmVzOwogICAgfQogICAgd2hpbGUoeDItLT4wKSB7CiAgICAgICAgcmVzICo9MzsKICAgICAgICBpZihyZXM+SU5GKSByZXR1cm4gcmVzOwogICAgfQogICAgd2hpbGUoeDMtLT4wKSB7CiAgICAgICAgcmVzICo9NTsKICAgICAgICBpZihyZXM+SU5GKSByZXR1cm4gcmVzOwogICAgfQogICAgd2hpbGUoeDQtLT4wKSB7CiAgICAgICAgcmVzKj03OwogICAgICAgIGlmKHJlcz5JTkYpIHJldHVybiByZXM7CiAgICB9CiAgICByZXR1cm4gcmVzOwp9CgppbnQgZ28oaW50IHAsIGJvb2wgeiwgYm9vbCBnLCBpbnQgYTIsIGludCBhMywgaW50IGE1LGludCBhNykgewogICAgaWYocD09LTEpIHJldHVybiB6ICYmIChhMj09MCkgJiYgKGEzPT0wKSAmJiAoYTU9PTApJiYgKGE3PT0wKTsKICAgIGludCAmcmVzID0gZHBbcF1bel1bZ11bYTJdW2EzXVthNV1bYTddOwogICAgaWYocmVzPj0wKSByZXR1cm4gcmVzOwogICAgcmVzID0gMDsKICAgIGlmKCF6KSByZXMgPSBnbyhwLTEseixnIHx8ICgwPGJbcF0pLGEyLGEzLGE1LGE3KTsKICAgIGZvcihpbnQgaT0xO2k8PTk7IGkrKykgewogICAgICAgIGlmKGcgfHwoaTw9YltwXSkpIAogICAgICAgIHsKICAgICAgICAgICAgaW50IGIyID0gYTIsYjM9YTMsIGI1PWE1LCBiNz1hNzsKICAgICAgICAgICAgaWYoaSU4PT0wKSBiMi09MzsKICAgICAgICAgICAgZWxzZSBpZihpJTQ9PTApIGIyLT0yOwogICAgICAgICAgICAgICAgZWxzZSBpZihpJTI9PTApIGIyLS07CiAgICAgICAgICAgICAgICBpZihpJTk9PTApIGIzLT0yOwogICAgICAgICAgICAgICAgZWxzZSBpZihpJTM9PTApIGIzLS07CiAgICAgICAgICAgICAgICBpZihpJTU9PTApIGI1LS07CiAgICAgICAgICAgICAgICBpZihpJTc9PTApIGI3LS07CiAgICAgICAgICAgICAgICBpZihiMj49MCAmJiBiMz49MCAmJiBiNT49MCAmJiBiNz49MCkgewogICAgICAgIHJlcys9Z28ocC0xLDEsZ3x8KGk8YltwXSksYjIsYjMsYjUsYjcpOwogICAgICAgICAgICB9CiAgICAgICAgCiAgICAgICAgfQogICAgfQogICAgcmV0dXJuIHJlczsKfQoKaW50IG1haW4oKSB7CiAgICAvKiBFbnRlciB5b3VyIGNvZGUgaGVyZS4gUmVhZCBpbnB1dCBmcm9tIFNURElOLiBQcmludCBvdXRwdXQgdG8gU1RET1VUICovICAKICAgIGludCB0OwogICAgY2luPj50OwogICAgd2hpbGUodC0tPjApIHsKICAgICAgICBtZW1zZXQoZHAsLTEsc2l6ZW9mKGRwKSk7CiAgICBpbnQgcmV0ID0wOwogICAgaW50IG47CiAgICBjaW4+Pm47CiAgICBmb3IoaW50IGk9MDsgaTw9MTE7aSsrKSB7CiAgICAgICAgYltpXT0gbiUxMDsKICAgICAgICBuLz0xMDsKICAgIH0KICAgIGZvcihpbnQgaT0wO2k8PWFbMF07IGkrKykgewogICAgICAgIGZvcihpbnQgaj0wO2o8PWFbMV07IGorKykgewogICAgICAgICAgICBmb3IoaW50IGs9MDsgazw9YVsyXTtrKyspIHsKICAgICAgICAgICAgICAgIGZvcihpbnQgbD0wO2w8PWFbM107IGwrKyl7IAogICAgICAgICAgICAgICAgICAgIGxsIHJlcyA9IGdldChpLGosayxsKTsKICAgICAgICAgICAgICAgICAgICBpZihyZXM+PUlORiljb250aW51ZTsKICAgICAgICAgICAgICAgICAgICBpbnQgY3VyID0gcmVzOwogICAgICAgICAgICAgICAgICAgIGludCBhbnMgPSBnbygxMCwwLDAsaSxqLGssbCk7CiAgICAgICAgICAgICAgICAgICAgaW50IHBoaSA9IGN1ciwgZGl2ID0gMTsKICAgICAgICAgICAgICAgICAgICBmb3IoaW50IG09MjttKm08PWN1cjsgbSsrKSB7CiAgICAgICAgICAgICAgICAgICAgICAgIGlmKGN1ciVtPT0wKSB7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICBpbnQgdG90ID0gMDsKICAgICAgICAgICAgICAgICAgICAgICAgICAgIHdoaWxlKGN1ciVtPT0wKSB7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgY3VyLz1tOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHRvdCsrOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgICAgICAgICAgICAgcGhpIC89bTsKICAgICAgICAgICAgICAgICAgICAgICAgICAgIHBoaSo9KG0tMSk7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICBkaXYgKj0gKHRvdCsxKTsKICAgICAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgICAgICBpZihjdXI+MSkgewogICAgICAgICAgICAgICAgICAgICAgICBwaGkgLz1jdXI7CiAgICAgICAgICAgICAgICAgICAgICAgIHBoaSAqPSAoY3VyLTEpOwogICAgICAgICAgICAgICAgICAgICAgICBkaXYgKj0gMjsKICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICAgcmV0PShyZXQrKChhbnMqMUxMKnBoaSklbW9kKSoxTEwqZGl2KSVtb2Q7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICB9CiAgICBjb3V0PDxyZXQ8PGVuZGw7CiAgICB9CiAgICByZXR1cm4gMDsKfQ==