#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==