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