#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
typedef  long long ll;
typedef  vector<int> vi;
typedef  pair<int,int> pii;
typedef  pair<ll,int> pli;
typedef  pair<int,string> pis;
double   pi=3.1415926535898;
#define speed      ios::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL);
#define lop(i,n)    for(int i=0;i<int(n);i++)
#define ff(i,a,b)  for(int i=a;i<=int(b);++i)
#define fr(i,a,b)  for(int i=a;i>=int(b);i--)
#define ms(x,a)    memset(x,a,sizeof(x))
#define all(x)     (x).begin(),(x).end()
#define sz(x)      int(x.size())
#define pb         push_back
#define r0         return 0;
#define CC         continue;
#define bb(x)      cerr<< x <<endl;
#define f          first
//#define s          second       //  __builtin_popcount;
//freopen("input.txt","r",stdin),freopen("output.txt","w",stdout);
string ys = "YES\n";
string no = "NO\n" ;
const double EPS = 1e-6;
const int inf = 1<<30;
const ll M  = 1e9+7 ;
const int N = 100100;
/////  for (int i= -inf ; i < inf ; i++)   Hi  :P
 
int mem[111][555];
int dp (int n, int s)
{
    if ( n == 0 )
    {
        return s != 0;
    }
    int &r = mem[n][s];
    if ( r != -1)
    {
        return r;
    }
    r = 0;
    ff(i,1,n)
    {
        r += dp(n-i,s^i);
        r %= M;
    }
    return r;
}
 
main()
{
    int t;ms(mem,-1);
    cin >> t;
    while(t--)
    {
        int n;
        cin >> n;
        cout << dp(n,0) << endl;
    }
 
}

I3ByYWdtYSBHQ0Mgb3B0aW1pemUoIk8zIikKI2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnR5cGVkZWYgIGxvbmcgbG9uZyBsbDsKdHlwZWRlZiAgdmVjdG9yPGludD4gdmk7CnR5cGVkZWYgIHBhaXI8aW50LGludD4gcGlpOwp0eXBlZGVmICBwYWlyPGxsLGludD4gcGxpOwp0eXBlZGVmICBwYWlyPGludCxzdHJpbmc+IHBpczsKZG91YmxlICAgcGk9My4xNDE1OTI2NTM1ODk4OwojZGVmaW5lIHNwZWVkICAgICAgaW9zOjpzeW5jX3dpdGhfc3RkaW8oZmFsc2UpO2Npbi50aWUoTlVMTCk7IGNvdXQudGllKE5VTEwpOwojZGVmaW5lIGxvcChpLG4pICAgIGZvcihpbnQgaT0wO2k8aW50KG4pO2krKykKI2RlZmluZSBmZihpLGEsYikgIGZvcihpbnQgaT1hO2k8PWludChiKTsrK2kpCiNkZWZpbmUgZnIoaSxhLGIpICBmb3IoaW50IGk9YTtpPj1pbnQoYik7aS0tKQojZGVmaW5lIG1zKHgsYSkgICAgbWVtc2V0KHgsYSxzaXplb2YoeCkpCiNkZWZpbmUgYWxsKHgpICAgICAoeCkuYmVnaW4oKSwoeCkuZW5kKCkKI2RlZmluZSBzeih4KSAgICAgIGludCh4LnNpemUoKSkKI2RlZmluZSBwYiAgICAgICAgIHB1c2hfYmFjawojZGVmaW5lIHIwICAgICAgICAgcmV0dXJuIDA7CiNkZWZpbmUgQ0MgICAgICAgICBjb250aW51ZTsKI2RlZmluZSBiYih4KSAgICAgIGNlcnI8PCB4IDw8ZW5kbDsKI2RlZmluZSBmICAgICAgICAgIGZpcnN0Ci8vI2RlZmluZSBzICAgICAgICAgIHNlY29uZCAgICAgICAvLyAgX19idWlsdGluX3BvcGNvdW50OwovL2ZyZW9wZW4oImlucHV0LnR4dCIsInIiLHN0ZGluKSxmcmVvcGVuKCJvdXRwdXQudHh0IiwidyIsc3Rkb3V0KTsKc3RyaW5nIHlzID0gIllFU1xuIjsKc3RyaW5nIG5vID0gIk5PXG4iIDsKY29uc3QgZG91YmxlIEVQUyA9IDFlLTY7CmNvbnN0IGludCBpbmYgPSAxPDwzMDsKY29uc3QgbGwgTSAgPSAxZTkrNyA7CmNvbnN0IGludCBOID0gMTAwMTAwOwovLy8vLyAgZm9yIChpbnQgaT0gLWluZiA7IGkgPCBpbmYgOyBpKyspICAgSGkgIDpQCgppbnQgbWVtWzExMV1bNTU1XTsKaW50IGRwIChpbnQgbiwgaW50IHMpCnsKICAgIGlmICggbiA9PSAwICkKICAgIHsKICAgICAgICByZXR1cm4gcyAhPSAwOwogICAgfQogICAgaW50ICZyID0gbWVtW25dW3NdOwogICAgaWYgKCByICE9IC0xKQogICAgewogICAgICAgIHJldHVybiByOwogICAgfQogICAgciA9IDA7CiAgICBmZihpLDEsbikKICAgIHsKICAgICAgICByICs9IGRwKG4taSxzXmkpOwogICAgICAgIHIgJT0gTTsKICAgIH0KICAgIHJldHVybiByOwp9CgptYWluKCkKewogICAgaW50IHQ7bXMobWVtLC0xKTsKICAgIGNpbiA+PiB0OwogICAgd2hpbGUodC0tKQogICAgewogICAgICAgIGludCBuOwogICAgICAgIGNpbiA+PiBuOwogICAgICAgIGNvdXQgPDwgZHAobiwwKSA8PCBlbmRsOwogICAgfQoKfQ==