f=lambda n,k=0,m=2,p=1:k/n or-~f(n,k+p%m*(`n`in`m`),m+1,p*m*m)

import sys
sys.setrecursionlimit(10000)

for i in range(1, 21):
	print '%2d %4d'%(i, f(i))