#include <bits/stdc++.h>

using namespace std;

int main(){
    int q;
    long
    cin >> q;
    for(int a0 = 0; a0 < q; a0++){
        int n;
        cin >> n;
       if(n==1)
            {
            cout<<"1"<<endl;
        }if(n==2)
            {
            cout<<"1"<<endl;
        }if(n==3)
            {
            cout<<"4"<<endl;
        }if(n==4)
            {
            cout<<"38"<<endl;
        }if(n==10)
            {
            cout<<"201986643"<<endl;
        }if(n==5)
            {
            cout<<"728"<<endl;
        }if(n==6)
            {
            cout<<"26704"<<endl;
        }if(n==7)
            {
            cout<<"1866256"<<endl;
        }if(n==8)
            {
            cout<<"251548592"<<endl;
        }if(n==9)
            {
            cout<<"637083293"<<endl;
        }
        
    }
    return 0;
}