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))
Zj1sYW1iZGEgbixrPTQsbT02LHA9WzMsMl06MS9uIG9yIG4lcFsxXWFuZCBmKG4saysxLG0qayxtKm0laypba10rcClvciBwW2xlbihwKSoyJTRdKmYobi9wWzFdKQoKaW1wb3J0IHN5cwpzeXMuc2V0cmVjdXJzaW9ubGltaXQoMTAwMDApCgpmb3IgbiBpbiAoMSwgMiwgMywgMTAsIDM3LCAzNjAsIDEyMzQ1LCA2Nzg5NTY3OCk6CglwcmludCAnJThkIC0+ICU5ZCcgJSAobiwgZihuKSk=