a,b,c,d=0,0,0,1;rs=[1]
5000.times{rs<<a%17;a,b,c,d=b,c,d,a+b+c+d}
gets.to_i.times{p rs[gets.to_i%4912]}