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