#include <stdio.h>
 
g(a,b){return!a?b:g(b%a,a);}
i;r;f(n){for(i=2,r=1;i<n;i++)r+=(g(i,n)==1);}
t;k;s(m){for(k=m,t=0;!t&(k<m*m);)f(++k),t=(r==m);}

main()
{
	for(int x=1; x<50; x++)
	{
		s(x);
		
		if(t) printf(" %d ~ phi(%d) \n", x, k);
	}
}