""" 1---3---5---7--9--.....(2n-1) 1s--2s--3s--4s--5s.....第n秒 路程=[1+2n-1]*n/2=n**2 """ t=int(input()) for i in range(t): n=int(input()) print(n**2%10000)