I created a Python solution that passes 10^12 tests but always gets timeout in 10^18 tests. The step 1 of the solution is prime factorization for m. Step 1 is just 1/10 lines of code in the entire solution, however, step 1 takes the majority of the running time because prime factorization is a known hard problem and it is the basis of RSA encryption.

In my solution, the prime factorization is O(sqrt(m)) time complexity. So for 10^18 tests, it's a 10^9 loop, which is close to Python language's capacity.

Prime factorization seems a neccesary step to me. I think the only way to pass the kata is to optimize the prime factorization step. However, it might not be possible in a slow language like Python. Even if optimization is possible, it might be overcomplicated for a 3 kyu problem.