1
31

142908549

这组过不去

#include<bits/stdc++.h>
using namespace std;
// #pragma GCC optimize(1)
// #pragma GCC optimize(2)
// #pragma GCC optimize(3,"Ofast")
#define int long long
#define y0 Y0
#define y1 Y1
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define min(a,b) (a<b?a:b) 
#define max(a,b) (a>b?a:b)
#define P pair<int,int>
#define x first
#define y second
#define modd(x) (((x)%mod+mod)%mod) 
#define rd read()
#define lowbit(x) ((x)&(-x))
#define abs(x) ((x)<0?-(x):(x))
#define submod(x,y,mod) (((x-=y)<0)&&(x+=mod))
#define addmod(x,y,mod) (((x+=y)>=mod)&&(x-=mod))
mt19937 rnd(time(0));
char buf[1<<23],*p1=buf,*p2=buf,obuf[1<<23],*O=obuf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
inline int read(int u=0, char c=getchar(), bool f=false){
    for(;!isdigit(c);c=getchar()) f|=c=='-';
    for(;isdigit(c);c=getchar()) u=(u<<1)+(u<<3)+(c^'0');
    return f?-u:u;
}
inline void wt(int x){
    if(x<0) x=-x,putchar('-');
    if(x>9) wt(x/10);
    putchar((x%10)^'0');
}
inline void wt(int x,char k){wt(x),putchar(k);}
const int inf=~0U>>1,linf=~0ULL>>1;
const int mod=999999893,g=3,gi=332748118;
const int N=2e5+10;
struct node{
    int x,y;
};
node operator%(const node a,const int p){return {(a.x%p+p)%p,(a.y%p+p)%p};}
node operator+(const node a,const node b){return (node){a.x+b.x,a.y+b.y};}
node operator-(const node a,const node b){return (node){a.x-b.x,a.y-b.y};}
node operator*(const node a,const node b){return (node){a.x*b.x+2*a.y*b.y,a.x*b.y+a.y*b.x};}
node power(node x,int k){
    node res={1,0};
    while(k){
        if(k&1) res=res*x%mod;
        x=x*x%mod;
        k>>=1;
    }
    return res;
}
int power(int x,int k){
    int res=1;
    while(k){
        if(k&1) res=res*x%mod;
        x=x*x%mod;
        k>>=1;
    }
    return res;
}
node operator/(const node a,const node b){
    int u=power(b.x*b.x-2*b.y*b.y,mod-2);
    return (node){(b.x*a.x-2*b.y*a.y)%mod*u%mod,(b.x*a.y-b.y*a.x)%mod*u%mod}%mod;
}
int n,T;
void work(){
    n=rd;
    node m=(node)(power((node){0,1},n-1)-(node){1,0})%mod*(node){1,1}%mod*(node){2,0}%mod,
    v=(node)(m+(node){0,2})%mod;
    wt((m/v).y,'\n');
}
main(){
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    T=rd;
    while(T--) work();
    return 0;
}