Problem link: here
The best way I could think of right now is factorizing using pollard rho and then do O(N*D) dp where D is number of divisors. Problem is D can be up to almost 10^5 for some highly composite numbers. Any help is appreciated, thanks!