#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#define x 100000
int main() {

   unsigned long long int t,n,ans=1,k=0;
    scanf("%llu",&t);
    while(t--)
      { scanf("%llu",&n);
        if(n<64)
        printf("%llu\n",(unsigned long long int)pow(2,n)%x-1);
        else if(n==64)
            printf("51615\n");
        else
            {   ans=1;
                k=n/64;
               while(k--)
                { ans*=51616;
                  ans=ans%x;
                }
             ans*=((unsigned long long int)pow(2,n%64)%x);
             ans=ans%x;
             printf("%llu\n",ans-1);
                
      }
}