T=int(input()) for _ in range(T): n = int(input()) k=1 s=0 for i in range(n): s=(s+k)%10000 k=k+2 print(s)