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