Finding inverse

def gcd(aa, bb):
    while (aa != 0):
        tmp = aa
        aa = bb % aa
        bb = tmp
    return bb

def totient(nn):
    result = 1
    for ii in range(2, nn):
        if (gcd(ii, nn) == 1):
            result += 1
    return result


def isPrime(nn):
    if (nn % 2 == 0): return False
    pp = 3
    while (pp * pp < nn):
        if (nn % pp == 0): return False
        pp += 2
    return True

def main(num, mod):
    ret = 0
    if isPrime(mod):
        ret = pow(num, mod-2, mod)
    else:
        toti = totient(mod)
        if toti == 2:
            ret = -1
        else:
            ret = pow(num, toti - 1, mod)
    return ret

if __name__ == "__main__":
    num, mod = [int(aa) for aa in input().split(" ")]
    ret = main(num, mod)
    print(ret)

Test 1

Verdict: ACCEPTED

Test 2

Verdict: WRONG ANSWER

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: WRONG ANSWER

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: WRONG ANSWER

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: WRONG ANSWER

Test 12

Verdict: TIME LIMIT EXCEEDED

Test 13

Verdict: TIME LIMIT EXCEEDED

Test 14

Verdict: TIME LIMIT EXCEEDED