f=lambda n,k=4,m=6,p=[3,2]:1/n or n%p[1]and f(n,k+1,m*k,m*m%k*[k]+p)or p[len(p)*2%4]*f(n/p[1])

import sys
sys.setrecursionlimit(10000)

for n in (1, 2, 3, 10, 37, 360, 12345, 67895678):
	print '%8d -> %9d' % (n, f(n))