sub f{my@r;
	for$y(0..3){
		for$x(0..3){
			for(0..3){
				($r[4*$y+$x]+=$Z[4*$y+$_]*$_[4*$_+$x])%=17
			}
		}
	}
	@Z=@r
}

<>;
for(<>){
	$n=$_-1;
	@Z=(1,0,0,0,
	    0,1,0,0,
	    0,0,1,0,
	    0,0,0,1);
	f(@Z),$n>>$_&1&&f(1,1,1,1,
	                  1,0,0,0,
	                  0,1,0,0,
	                  0,0,1,0)for reverse 0..59;
	print$Z[12],$/
}