#yuki657 def tet(n): a,b,c,d=0,0,0,1 if n<4: return 0 if n==4: return 1 for i in xrange(5,n+1): temp=(a+b+c+d)%17 a,b,c,d=b,c,d,temp return d q=int(raw_input()) for i in xrange(q): m=int(raw_input()) print tet(m)%17