#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

typedef long long LL;

const int MOD = 1e5;

LL f(LL a,LL b)

{

    LL res=;

    while(b!=)

    {

        if(b%==) res=res*a%MOD;

        a=a*a%MOD;

        b/=;

    }

    return res;

}

int main(void)

{

    LL n;

    int t;

    scanf("%d",&t);

    while(t--)

    {

        scanf("%lld",&n);

        n=f(n,n)%;

        printf("%d\n",n);

    }

    return ;

}