T = int(input()) for _ in range(T): n = int(input()) a = n * (n + 1) // 2 a_s = a % 10000 print(a_s)