require 'prime' N_MAX = 110 $mp = Array.new(N_MAX).map{Array.new(N_MAX,0)} $used = Array.new(N_MAX).map{Array.new(N_MAX,false)} $n = gets.chomp.to_i $vx = [1,0,-1,0] $vy = [0,1,0,-1] def dfs(w,h,y,x) return false if y<0 || x<0 || y>=h || x>=w return false if $used[y][x] $used[y][x] = true return false if $mp[y][x]==1e9 return true if $mp[y][x]==$n t = $mp[y][x] return false if isP_MR(t) for i in 0...4 return true if dfs(w,h,y+$vy[i],x+$vx[i]) end return false end def powmod(a,b,m) return 1 if b==0 p = powmod(a,b/2,m) p = p*p%m p = p*a%m if b%2==0 return p end # http://d.hatena.ne.jp/pashango_p/20090704/1246692091 def isP_MR(q) k = 10000 return Prime.prime?(q) if q<10000000 return false if q&1==0 d = (q-1)>>1 while d&1==0 d>>=1 end for i in 0...k a = rand(q-2)+1 t = d y = powmod(a,t,q) while t!=q-1 && y!=1 && y!=q-1 y = powmod(y,2,q) t <<= 1 end if y!=q-1 && t&1==0 return false end end return true end if $n<100 for w in 3...$n h = $n/w + ( $n%w == 0 ? 0 : 1 ) for i in 0...N_MAX for j in 0...N_MAX $mp[i][j] = 1e9 if i