# pollard p-1 factoring method
 
def ilog(b, n): # max e where b**e <= n
    lo, blo, hi, bhi = 0, 1, 1, b
    while bhi < n:
        lo, blo, hi, bhi = hi, bhi, hi+hi, bhi*bhi
    while 1 < (hi - lo):
        mid = (lo + hi) // 2
        bmid = blo * pow(b, (mid - lo))
        if n < bmid: hi, bhi = mid, bmid
        elif bmid < n: lo, blo = mid, bmid
        else: return mid
    if bhi == n: return hi
    return lo
 
def gcd(a,b): # euclid's algorithm
    if b == 0: return a
    return gcd(b, a%b)
 
def primegen(start=0): # stackoverflow.com/a/20660551
    if start <= 2: yield 2    # prime (!) the pump
    if start <= 3: yield 3    # prime (!) the pump
    ps = primegen()           # sieving primes
    p = next(ps) and next(ps) # first sieving prime
    q = p * p; D = {}         # initialization
    def add(m, s):            # insert multiple/stride
        while m in D: m += s  #   find unused multiple
        D[m] = s              #   save multiple/stride
    while q <= start:         # initialize multiples
        x = (start // p) * p  #   first multiple of p
        if x < start: x += p  #   must be >= start
        if x % 2 == 0: x += p #   ... and must be odd
        add(x, p+p)           #   insert in sieve
        p = next(ps)          #   next sieving prime
        q = p * p             #   ... and its square
    c = max(start-2, 3)       # first prime candidate
    if c % 2 == 0: c += 1     # must be odd
    while True:               # generate infinite list
        c += 2                #   next odd candidate
        if c in D:            #   c is composite
            s = D.pop(c)      #     fetch stride
            add(c+s, s)       #     add next multiple
        elif c < q: yield c   #   c is prime; yield it
        else: # (c == q)      #   add p to sieve
            add(c+p+p, p+p)   #     insert in sieve
            p = next(ps)      #     next sieving prime
            q = p * p         #     ... and its square
 
def pminus1(n, b, x=2):
    q = 0; pgen = primegen(); p = next(pgen)
    while p < b:
        x = pow(x, p**ilog(p,b), n)
        q, p = p, next(pgen)
    g = gcd(x-1, n)
    if 1 < g < n: return g
    return False
 
print pminus1(10001, 10)
 
print pminus1(834126253476422235279396896780306823377996256349,125000)# your code goes here

IyBwb2xsYXJkIHAtMSBmYWN0b3JpbmcgbWV0aG9kCgpkZWYgaWxvZyhiLCBuKTogIyBtYXggZSB3aGVyZSBiKiplIDw9IG4KICAgIGxvLCBibG8sIGhpLCBiaGkgPSAwLCAxLCAxLCBiCiAgICB3aGlsZSBiaGkgPCBuOgogICAgICAgIGxvLCBibG8sIGhpLCBiaGkgPSBoaSwgYmhpLCBoaStoaSwgYmhpKmJoaQogICAgd2hpbGUgMSA8IChoaSAtIGxvKToKICAgICAgICBtaWQgPSAobG8gKyBoaSkgLy8gMgogICAgICAgIGJtaWQgPSBibG8gKiBwb3coYiwgKG1pZCAtIGxvKSkKICAgICAgICBpZiBuIDwgYm1pZDogaGksIGJoaSA9IG1pZCwgYm1pZAogICAgICAgIGVsaWYgYm1pZCA8IG46IGxvLCBibG8gPSBtaWQsIGJtaWQKICAgICAgICBlbHNlOiByZXR1cm4gbWlkCiAgICBpZiBiaGkgPT0gbjogcmV0dXJuIGhpCiAgICByZXR1cm4gbG8KCmRlZiBnY2QoYSxiKTogIyBldWNsaWQncyBhbGdvcml0aG0KICAgIGlmIGIgPT0gMDogcmV0dXJuIGEKICAgIHJldHVybiBnY2QoYiwgYSViKQoKZGVmIHByaW1lZ2VuKHN0YXJ0PTApOiAjIHN0YWNrb3ZlcmZsb3cuY29tL2EvMjA2NjA1NTEKICAgIGlmIHN0YXJ0IDw9IDI6IHlpZWxkIDIgICAgIyBwcmltZSAoISkgdGhlIHB1bXAKICAgIGlmIHN0YXJ0IDw9IDM6IHlpZWxkIDMgICAgIyBwcmltZSAoISkgdGhlIHB1bXAKICAgIHBzID0gcHJpbWVnZW4oKSAgICAgICAgICAgIyBzaWV2aW5nIHByaW1lcwogICAgcCA9IG5leHQocHMpIGFuZCBuZXh0KHBzKSAjIGZpcnN0IHNpZXZpbmcgcHJpbWUKICAgIHEgPSBwICogcDsgRCA9IHt9ICAgICAgICAgIyBpbml0aWFsaXphdGlvbgogICAgZGVmIGFkZChtLCBzKTogICAgICAgICAgICAjIGluc2VydCBtdWx0aXBsZS9zdHJpZGUKICAgICAgICB3aGlsZSBtIGluIEQ6IG0gKz0gcyAgIyAgIGZpbmQgdW51c2VkIG11bHRpcGxlCiAgICAgICAgRFttXSA9IHMgICAgICAgICAgICAgICMgICBzYXZlIG11bHRpcGxlL3N0cmlkZQogICAgd2hpbGUgcSA8PSBzdGFydDogICAgICAgICAjIGluaXRpYWxpemUgbXVsdGlwbGVzCiAgICAgICAgeCA9IChzdGFydCAvLyBwKSAqIHAgICMgICBmaXJzdCBtdWx0aXBsZSBvZiBwCiAgICAgICAgaWYgeCA8IHN0YXJ0OiB4ICs9IHAgICMgICBtdXN0IGJlID49IHN0YXJ0CiAgICAgICAgaWYgeCAlIDIgPT0gMDogeCArPSBwICMgICAuLi4gYW5kIG11c3QgYmUgb2RkCiAgICAgICAgYWRkKHgsIHArcCkgICAgICAgICAgICMgICBpbnNlcnQgaW4gc2lldmUKICAgICAgICBwID0gbmV4dChwcykgICAgICAgICAgIyAgIG5leHQgc2lldmluZyBwcmltZQogICAgICAgIHEgPSBwICogcCAgICAgICAgICAgICAjICAgLi4uIGFuZCBpdHMgc3F1YXJlCiAgICBjID0gbWF4KHN0YXJ0LTIsIDMpICAgICAgICMgZmlyc3QgcHJpbWUgY2FuZGlkYXRlCiAgICBpZiBjICUgMiA9PSAwOiBjICs9IDEgICAgICMgbXVzdCBiZSBvZGQKICAgIHdoaWxlIFRydWU6ICAgICAgICAgICAgICAgIyBnZW5lcmF0ZSBpbmZpbml0ZSBsaXN0CiAgICAgICAgYyArPSAyICAgICAgICAgICAgICAgICMgICBuZXh0IG9kZCBjYW5kaWRhdGUKICAgICAgICBpZiBjIGluIEQ6ICAgICAgICAgICAgIyAgIGMgaXMgY29tcG9zaXRlCiAgICAgICAgICAgIHMgPSBELnBvcChjKSAgICAgICMgICAgIGZldGNoIHN0cmlkZQogICAgICAgICAgICBhZGQoYytzLCBzKSAgICAgICAjICAgICBhZGQgbmV4dCBtdWx0aXBsZQogICAgICAgIGVsaWYgYyA8IHE6IHlpZWxkIGMgICAjICAgYyBpcyBwcmltZTsgeWllbGQgaXQKICAgICAgICBlbHNlOiAjIChjID09IHEpICAgICAgIyAgIGFkZCBwIHRvIHNpZXZlCiAgICAgICAgICAgIGFkZChjK3ArcCwgcCtwKSAgICMgICAgIGluc2VydCBpbiBzaWV2ZQogICAgICAgICAgICBwID0gbmV4dChwcykgICAgICAjICAgICBuZXh0IHNpZXZpbmcgcHJpbWUKICAgICAgICAgICAgcSA9IHAgKiBwICAgICAgICAgIyAgICAgLi4uIGFuZCBpdHMgc3F1YXJlCgpkZWYgcG1pbnVzMShuLCBiLCB4PTIpOgogICAgcSA9IDA7IHBnZW4gPSBwcmltZWdlbigpOyBwID0gbmV4dChwZ2VuKQogICAgd2hpbGUgcCA8IGI6CiAgICAgICAgeCA9IHBvdyh4LCBwKippbG9nKHAsYiksIG4pCiAgICAgICAgcSwgcCA9IHAsIG5leHQocGdlbikKICAgIGcgPSBnY2QoeC0xLCBuKQogICAgaWYgMSA8IGcgPCBuOiByZXR1cm4gZwogICAgcmV0dXJuIEZhbHNlCgpwcmludCBwbWludXMxKDEwMDAxLCAxMCkKCnByaW50IHBtaW51czEoODM0MTI2MjUzNDc2NDIyMjM1Mjc5Mzk2ODk2NzgwMzA2ODIzMzc3OTk2MjU2MzQ5LDEyNTAwMCkjIHlvdXIgY29kZSBnb2VzIGhlcmU=