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