#include using namespace std; using ll = long long; using ull = unsigned long long; #define rep(i,a) for(int i=0;i<(a);i++) #define MOD 1000000007 const int NMAX=1000001; ll T[NMAX]; int main(){ T[4]=1; rep(i,NMAX-5){ (T[i+5]=T[i+4]+T[i+3]+T[i+2]+T[i+1])%=17; } int Q; cin>>Q; rep(i,Q){ ll n; cin>>n; ((--n)%=4912)++; cout<