def modularInverse(b, p):
    return pow(b, p-2, p)
 
def isPrime(p):
    return len([z for z in xrange(1,p + 1) if p % z == 0]) == 2
 
 
for p in xrange(2,100):
    if isPrime(p):
        for q in xrange(1, p):
            k = modularInverse(q, p)
            if (k < 1) or (k >= p):
                print "ModInv(%d, %d) = %d is out of range." % (q, p, k)
                exit(2)
            if ((k * q) % p) != 1:
                print "ModInv(%d, %d) is not %d." % (q, p, k)
                exit(2)
        print "Verified for %d!" % p

ZGVmIG1vZHVsYXJJbnZlcnNlKGIsIHApOgogICAgcmV0dXJuIHBvdyhiLCBwLTIsIHApCgpkZWYgaXNQcmltZShwKToKICAgIHJldHVybiBsZW4oW3ogZm9yIHogaW4geHJhbmdlKDEscCArIDEpIGlmIHAgJSB6ID09IDBdKSA9PSAyCgoKZm9yIHAgaW4geHJhbmdlKDIsMTAwKToKICAgIGlmIGlzUHJpbWUocCk6CiAgICAgICAgZm9yIHEgaW4geHJhbmdlKDEsIHApOgogICAgICAgICAgICBrID0gbW9kdWxhckludmVyc2UocSwgcCkKICAgICAgICAgICAgaWYgKGsgPCAxKSBvciAoayA+PSBwKToKICAgICAgICAgICAgICAgIHByaW50ICJNb2RJbnYoJWQsICVkKSA9ICVkIGlzIG91dCBvZiByYW5nZS4iICUgKHEsIHAsIGspCiAgICAgICAgICAgICAgICBleGl0KDIpCiAgICAgICAgICAgIGlmICgoayAqIHEpICUgcCkgIT0gMToKICAgICAgICAgICAgICAgIHByaW50ICJNb2RJbnYoJWQsICVkKSBpcyBub3QgJWQuIiAlIChxLCBwLCBrKQogICAgICAgICAgICAgICAgZXhpdCgyKQogICAgICAgIHByaW50ICJWZXJpZmllZCBmb3IgJWQhIiAlIHA=