a=int(input()) for i in range(a): b=int(input()) d=2*(b-1)+1 c=(d+1)**2//4 if c>=10000: x=c%10000 print(x) else: print(c)