#include<bits/stdc++.h>

#define ll long long
#define rep(A,B,C) for(A=B;A<C;++A)
#define pii pair<int,int>
#define pll pair<ll,ll>

using namespace std;

/////////////////////////////////////////////////////
#define MOD (ll)(1e9+7)


ll T;
ll N;
ll dp[10101][20][4];
ll mtx[55][55],mtx2[55][55],mtx3[55][55];
ll i, j, k;


void calc(ll n){
    if(n==0)
        return;
    ll i, j, k;
    if(n&1){
        rep(i,0,21){
            rep(j,0,21){
                mtx3[i][j] = mtx[i][j];
                mtx[i][j] = 0;
            }
        }
        rep(i,0,21){
            rep(j,0,21){
                rep(k,0,21){
                    (mtx[i][j] += mtx3[i][k] * mtx2[k][j]) %= MOD;
                }
            }
        }
    }
    rep(i,0,21){
        rep(j,0,21){
            mtx3[i][j] = mtx2[i][j];
            mtx2[i][j] = 0;
        }
    }
    rep(i,0,21){
        rep(j,0,21){
            rep(k,0,21){
                (mtx2[i][j] += mtx3[i][k] * mtx3[k][j]) %= MOD;
            }
        }
    }
    /*
    printf("%lld\n", n);
    rep(i,0,21){
        rep(j,0,21){
            printf("%lld ", mtx2[i][j]);
        }
        printf("\n");
    }*/
    calc(n / 2);
}

void qqq(){

    scanf("%lld", &N);
    if(N<5){
        printf("0\n");
        return;
    }
    rep(i,0,21){
        rep(j,0,21){
            mtx[i][j] = mtx2[i][j] = 0;
            if(i<10){
                if((i^1)==j){
                    mtx2[i][j] = 1;
                }else if(i%2==0&&i<j&&(j%2==1||10<=j)){
                    mtx2[i][j] = 1;
                } 
            }else{
                if(i<=j){
                    mtx2[i][j] = 1;
                }
            }
        }
    }
    /*
    rep(i,0,21){
        rep(j,0,21){
            printf("%lld ", mtx2[i][j]);
        }
        printf("\n");
    }*/
    mtx[0][0] = 1;
    calc(N - 4);

    printf("%lld\n", mtx[0][20]);
}


int main(){
    scanf("%lld", &T);
    
    while(T--){
        qqq();
    }
    
    return 0;
}