#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 111539786 
struct matran{
    ll a[2][2];
    void print(){
            for(ll i=0;i<2;i++){
                    for(ll j=0;j<2;j++) cout<<a[i][j]<<" ";
                    cout<<'\n';
            }
    }
};
matran mot;
struct cap{
   ll u,u_plus_1;
   void print(){
           cout<<u<<" "<<u_plus_1<<'\n';
   }
};
matran prod(matran A,matran B){
        matran anss;
        anss.a[0][0]=(A.a[0][0]*B.a[0][0]%mod + A.a[0][1] * B.a[1][0]%mod+mod)%mod;
        anss.a[0][1]=(A.a[0][0]*B.a[0][1]%mod + A.a[0][1] * B.a[1][1]%mod+mod)%mod;
        anss.a[1][0]=(A.a[1][0]*B.a[0][0]%mod + A.a[1][1] * B.a[1][0]%mod+mod)%mod;
        anss.a[1][1]=(A.a[1][0]*B.a[0][1]%mod+ A.a[1][1] * B.a[1][1]%mod+mod)%mod;
        return anss;
}
matran po(matran X,ll n){
        matran res = X, ans = mot;
        while(n){
                if(n%2) ans = prod(ans,res);
                res = prod(res,res);
                n/=2;
        }
        return ans;
}
cap prod1(cap pp, matran X){
        cap ans;
        ans.u = (pp.u * X.a[0][0]%mod+pp.u_plus_1 * X.a[1][0]%mod+mod)%mod;
        ans.u_plus_1 =  (pp.u * X.a[1][0]%mod+pp.u_plus_1 * X.a[1][1]%mod+mod)%mod;
        return ans;
}
int main(){
      

        ll a,b,nn,testcase;
        cin>>testcase;
        for(ll qq=1;qq<=testcase;qq++){
        //  cin>>a>>b;
        cin>>nn;
      
        cap init;
        init.u = 1;
        init.u_plus_1 = 2;
        matran M;
        M.a[0][0]=0;
        M.a[0][1]=1;
        M.a[1][0]=1;
        M.a[1][1]=1;
        mot.a[0][0]=1;
        mot.a[0][1]=0;
        mot.a[1][0]=0;
        mot.a[1][1]=1;
       
        matran res = po(M,nn-1);
        cap ansss = prod1(init,res);
        cout<<ansss.u<<'\n';
   
        }

}