a=int(input()) for i in range(a): n=int(input()) s=0 y=1 for x in range(1,n+1): s+=y s=s%10000 y+=2 print(s)