a=[0,0,0,1]
for _ in range(4,10**6+1):a+=[sum(a[-4:])%17]
for _ in [0]*int(input()):print(a[~-int(input())])