The problem can be solved using Mobius function and inclusion-exclusion principle.
See the editorial for this problem and this gfg blog to get the answer. I did the same for the codechef problem.
3 Likes