#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main() {
    long a[]={1, 1, 1, 4, 38, 728, 26704, 1866256, 251548592, 637083293, 201986643, 445470011, 496133824, 277610150, 33326024, 620067058
};
    long t=0; cin>>t;
    long s;while(t--)
        {cin>>s;
        cout<<a[s%15]<<endl;}
    return 0;
}