n = int(input()) for x in range(n): m = int(input()) st =1 res = 0 for i in range(m): res +=st st +=2 print(res%10000)