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