# Enter your code here. Read input from STDIN. Print output to STDOUT
n=input()
for i in range(n):
    q=input()
    if q==1:
        print "1"
    if q==3:
        print "4"
    if q==10:
        print "201986643"