#include<cstdio> 
#include<iostream> 
using namespace std; 
int main() 
{ 
    long long ans; 
    int t,n,i; 
    scanf("%d",&t); 
    while(t--) 
    { 
        ans=1; 
        scanf("%d",&n); 
        for(i=0;i<n-1;i++) 
        { 
            ans=(ans*2%20140413)%20140413; 
        } 
        cout<<ans<<endl; 
    } 
    return 0; 
}