import java.util.*;
import java.lang.*;
import java.io.*;
class Fast_Modular_Exponentiation {
private int ans = 1;
public int Power(int b, int p, int mod) {
while (p > 0) {
if ((p & 1) == 1) {
ans = ((ans % mod) * b) % mod;
}
b = ((b % mod) * b) % mod;
p >>= 1;
}
return (ans % mod);
}
}
class Extract_Primes {
final private int MAX = 500000;
public boolean[] arr = new boolean[MAX + 1];
final private int LIMIT
= (int) Math.
sqrt(MAX
); public int[] primes = new int[MAX];
public int sz = 0;
private void E_primes() {
for (int i = 2; i <= MAX; i++) {
if (arr[i] == true) {
primes[sz++] = i;
}
}
}
public void Calculate_primes() {
for (int i = 0; i <= MAX; i++) {
arr[i] = true;
}
arr[0] = arr[1] = false;
for (int i = 2; i <= LIMIT;) {
if (arr[i] == true) {
for (int j = i + i; j <= MAX; j += i) {
arr[j] = false;
}
}
if (i == 2) {
i += 1;
} else {
i += 2;
}
}
E_primes();
}
}
class Number_Of_Positive_Factors {
private int cnt = 1;
private int ans = 1;
public int Factors(int no, Extract_Primes ob) {
int number = no;
for (int i
= 0; i
< ob.
sz && (ob.
primes[i
] <= (int)Math.
sqrt(number
)); i
++) { cnt = 1;
while (number % ob.primes[i] == 0) {
cnt++;
number /= ob.primes[i];
}
ans *= cnt;
}
if (number > 1) {
ans = ans * 2;
}
return (ans);
}
}
class Perfect_Numbers_Calculation {
private final int MAX = 500000;
boolean[] check = new boolean[MAX];
public void Perfect() {
check[0] = false;
for (int i = 1; i * i <= MAX; i++) {
check[i * i] = true;
}
}
}
public class Main {
public static void main
(String[] args
) { InputReader in = new InputReader(inputstream);
Extract_Primes ep = new Extract_Primes();
ep.Calculate_primes();
Perfect_Numbers_Calculation pnc = new Perfect_Numbers_Calculation();
pnc.Perfect();
int T;
T
= Integer.
parseInt(in.
readString()); for (int i = 1; i <= T; i++) {
Task solver = new Task();
solver.solve(i, in, out, ep, pnc);
}
out.close();
}
}
class Task {
public void solve
(int testno, InputReader in,
PrintWriter out, Extract_Primes ep, Perfect_Numbers_Calculation pnc
) { int N = in.readInt();
if (N == 1 || N == 2 || N == 3) {
out.println("1");
} else if (ep.arr[N] == true) {
out.println("1");
} else {
Number_Of_Positive_Factors nopf = new Number_Of_Positive_Factors();
int cnt = nopf.Factors(N, ep);
Fast_Modular_Exponentiation fme = new Fast_Modular_Exponentiation();
if (pnc.check[N] == false) {
int ans = fme.Power(N, (cnt - 2) / 2, 10000);
if (ans == 0) {
out.println("0000");
} else {
out.println(ans);
}
} else {
int mid
= (int) Math.
sqrt(N
); int ans = fme.Power(mid, (cnt - 2), 10000);
if (ans == 0) {
out.println("0000");
} else {
out.println(ans);
}
}
}
}
}
class InputReader {
private byte[] buf = new byte[1024];
private int curChar;
private int numChars;
this.stream = stream;
}
public int read() {
if (numChars == -1) {
throw new InputMismatchException();
}
if (curChar >= numChars) {
curChar = 0;
try {
numChars = stream.read(buf);
throw new InputMismatchException();
}
if (numChars <= 0) {
return -1;
}
}
return buf[curChar++];
}
public int readInt() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
int res = 0;
do {
if (c < '0' || c > '9') {
throw new InputMismatchException();
}
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
int c = read();
while (isSpaceChar(c)) {
c = read();
}
do {
res.appendCodePoint(c);
c = read();
} while (!isSpaceChar(c));
return res.toString();
}
public long readLong() {
return Long.
parseLong(readString
()); }
public double readDouble() {
return Double.
parseDouble(readString
()); }
public float readFloat() {
return Float.
parseFloat(readString
()); }
public static boolean isSpaceChar(int c) {
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
}