t = int(input()) m = [] for i in range(t): m.append(int(input())) for i in range(t): n = m[i] dst = 0 speed = 1 for j in range(n): dst+=speed speed+=2 print(dst%10000)