# prime power predicate
 
from random import randint
from fractions import gcd
 
def findWitness(n, k=5): # miller-rabin
    s, d = 0, n-1
    while d % 2 == 0:
        s, d = s+1, d/2
    for i in range(k):
        a = randint(2, n-1)
        x = pow(a, d, n)
        if x == 1 or x == n-1: continue
        for r in range(1, s):
            x = (x * x) % n
            if x == 1: return a
            if x == n-1: break
        else: return a
    return 0
 
# returns p,k such that n=p**k, or 0,0
# assumes n is an integer greater than 1
def primePower(n):
    def checkP(n, p):
        k = 0
        while n > 1 and n % p == 0:
            n, k = n / p, k + 1
        if n == 1: return p, k
        else: return 0, 0
    if n % 2 == 0: return checkP(n, 2)
    q = n
    while True:
        a = findWitness(q)
        if a == 0: return checkP(n, q)
        d = gcd(pow(a,q,n)-a, q)
        if d == 1 or d == q: return 0, 0
        q = d
 
print primePower(1940255363782247**37)

IyBwcmltZSBwb3dlciBwcmVkaWNhdGUKCmZyb20gcmFuZG9tIGltcG9ydCByYW5kaW50CmZyb20gZnJhY3Rpb25zIGltcG9ydCBnY2QKCmRlZiBmaW5kV2l0bmVzcyhuLCBrPTUpOiAjIG1pbGxlci1yYWJpbgogICAgcywgZCA9IDAsIG4tMQogICAgd2hpbGUgZCAlIDIgPT0gMDoKICAgICAgICBzLCBkID0gcysxLCBkLzIKICAgIGZvciBpIGluIHJhbmdlKGspOgogICAgICAgIGEgPSByYW5kaW50KDIsIG4tMSkKICAgICAgICB4ID0gcG93KGEsIGQsIG4pCiAgICAgICAgaWYgeCA9PSAxIG9yIHggPT0gbi0xOiBjb250aW51ZQogICAgICAgIGZvciByIGluIHJhbmdlKDEsIHMpOgogICAgICAgICAgICB4ID0gKHggKiB4KSAlIG4KICAgICAgICAgICAgaWYgeCA9PSAxOiByZXR1cm4gYQogICAgICAgICAgICBpZiB4ID09IG4tMTogYnJlYWsKICAgICAgICBlbHNlOiByZXR1cm4gYQogICAgcmV0dXJuIDAKCiMgcmV0dXJucyBwLGsgc3VjaCB0aGF0IG49cCoqaywgb3IgMCwwCiMgYXNzdW1lcyBuIGlzIGFuIGludGVnZXIgZ3JlYXRlciB0aGFuIDEKZGVmIHByaW1lUG93ZXIobik6CiAgICBkZWYgY2hlY2tQKG4sIHApOgogICAgICAgIGsgPSAwCiAgICAgICAgd2hpbGUgbiA+IDEgYW5kIG4gJSBwID09IDA6CiAgICAgICAgICAgIG4sIGsgPSBuIC8gcCwgayArIDEKICAgICAgICBpZiBuID09IDE6IHJldHVybiBwLCBrCiAgICAgICAgZWxzZTogcmV0dXJuIDAsIDAKICAgIGlmIG4gJSAyID09IDA6IHJldHVybiBjaGVja1AobiwgMikKICAgIHEgPSBuCiAgICB3aGlsZSBUcnVlOgogICAgICAgIGEgPSBmaW5kV2l0bmVzcyhxKQogICAgICAgIGlmIGEgPT0gMDogcmV0dXJuIGNoZWNrUChuLCBxKQogICAgICAgIGQgPSBnY2QocG93KGEscSxuKS1hLCBxKQogICAgICAgIGlmIGQgPT0gMSBvciBkID09IHE6IHJldHVybiAwLCAwCiAgICAgICAgcSA9IGQKCnByaW50IHByaW1lUG93ZXIoMTk0MDI1NTM2Mzc4MjI0NyoqMzcp