#include <bits/stdc++.h>
using namespace std;
#define lli long long int
const lli MOD=1e09+7; 
#define rep(i,n) for(int i=0;i<n;i++)
int main(){
    int t,n;
    cin>>t;
    while(t--){
    	cin>>n;
    	int k=9;
    	lli dp[k+1][n+1];
    	rep(i,k+1)rep(j,n+1)dp[i][j]=0;
    	rep(i,n+1)dp[0][i]=1;
    	for(int i=1;i<=k;i++){
    		dp[i][1]=1;// having length 1 ,total lucky numbers is 1 for each i = 1,2,3,4,5,6,7,8,9
    	}
    	for(int j=2;j<=n;j++){//having length varying from 2 to n
    		for(int i=1;i<=k;i++){// for i=1,2,3,4,5,6,7,8,9
    			if(i==k)dp[i][j]=dp[i-1][j-1]%MOD;//9 has only 8 no next,9->8 
    			else dp[i][j]=(dp[i-1][j-1]+dp[i+1][j-1])%MOD;//others has 2 8->7 and 8->9
    		}
    	}
    	lli ans=0;
    	for(int i=1;i<=k;i++){
    		ans+=dp[i][n];
    		ans%=MOD;
    	}
    	if(n==1)ans=(ans+1)%MOD;//if n==1 we include 0 
    	cout<<ans%MOD<<"\n";
    }
    return 0;
}