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.