t=int(input()) l=[] for i in range (t): n=int(input()) l.append(n) for i in l: k=1 o=1 for j in range (1,i): o+=2 k+=o print(k%10000)