#include<iostream> using namespace std; int compare(string a,string b){ if(a.length()>b.length()) return 1; else if(a.length()<b.length()) return -1; else return a.compare(b); } namespace hp{ } string add(string a,string b){ string res; int lena=a.size(),lenb=b.size(); if(lena<lenb) for(int i=1;i<=lenb-lena;i++) a="0"+a; else for(int i=1;i<=lena-lenb;i++) b="0"+b; lena=a.size(); int cf=0,temp; for(int i=lena-1;i>=0;i--){ temp=a[i]-'0'+b[i]-'0'+cf; cf=temp/10; temp%=10; res=char(temp+'0')+res; }if(cf!=0) res=char(cf+'0')+res; return res; } string sub(string a,string b){ string res; int tmp=a.length()-b.length(),cf=0; for(int i=b.length()-1;i>=0;i--){ if(a[tmp+i]<b[i]+cf){ res=char(a[tmp+i]-b[i]-cf+'0'+10)+res; cf=1; }else{ res=char(a[tmp+i]-b[i]-cf+'0')+res; cf=0; } }for(int i=tmp-1;i>=0;i--){ if(a[i]-cf>='0'){ res=char(a[i]-cf)+res; cf=0; }else{ res=char(a[i]-cf+10)+res; cf=1; } } res.erase(0,res.find_first_not_of('0')); return res; } string mul(string a,string b){ string res,tempstr; int lena=a.size(),lenb=b.size(); for(int i=lenb-1;i>=0;i--){ tempstr=""; int temp=b[i]-'0',t=0,cf=0; if(temp!=0){ for(int j=1;j<=lenb-1-i;j++) tempstr+="0"; for(int j=lena-1;j>=0;j--){ t=(temp*(a[j]-'0')+cf)%10; cf=(temp*(a[j]-'0')+cf)/10; tempstr=char(t+'0')+tempstr; }if(cf!=0) tempstr=char(cf+'0')+tempstr; } res=add(res,tempstr); } res.erase(0,res.find_first_not_of('0')); return res; } void divv(string a,string b,string &quo,string &rem){ quo=rem=""; if(b=="0"){ quo=rem="ERROR"; return; }if(a=="0"){ quo=rem="0"; return; } int res=compare(a,b); if(res<0){ quo="0"; rem=a; return; }else if(res==0){ quo="1"; rem="0"; return; }else{ int lena=a.length(),lenb=b.length(); string tempstr; tempstr.append(a,0,lenb-1); for(int i=lenb-1;i<lena;i++){ tempstr+=a[i]; tempstr.erase(0,tempstr.find_first_not_of('0')); if(tempstr.empty()) tempstr="0"; for(char ch='9';ch>='0';ch--){ string str,tmp; str+=ch; tmp=mul(b,str); if(compare(tmp,tempstr)<=0){ quo=quo+ch; tempstr=sub(tempstr,tmp); break; } } } rem=tempstr; } quo.erase(0,quo.find_first_not_of('0')); if(quo.empty()) quo="0"; } int main(){ int n; cin>>n; while(n--){ int k; cin>>k; string a="1",b="2"; for(int i=3;i<=k;i++){ string t=b; b=add(mul("2",b),a); a=t; } string temp,rem; divv(b,"32767",temp,rem); cout<<rem<<endl; } return 0; }