I think the solution starts here:

Think about a prime i, the answer will be m-m/i (the total less the number of multiples of i)

Now think about a composite i. I'll use as example 6. The answer is m-m/2-m/3+m/6. The answer is the same for 12.

So, you have a composite number that has factorization p1^c1*p2^c2...pk^ck, the answer for this number will be the same answer as the answer for the highest square-free number that divides this number (p1*p2*p3..*pk) because a number isn't coprime with another if and only if they share at least one prime factor. So the answer will be: m-m/p1-m/p2...-m/pk+m/(p1*p2)+m/(p1*p3)...+m/(p1*pk)-m/(p1*p2*p3).

You go through all the divisors and where there's an odd number of prime factors, you subtract. Otherwise you add. You can modify the sieve to group the numbers by their square-free factorization on the sieve and also get how many primes there are on the factorization.

Now you'll have a vector ans[n+1] that's initialized to 0. Do this for 1<=i<=n

If i==square_free[i], for j in divs[i] make ans[i]+=((-1)^primes[j])*m/(j)

total_ans+=ans[square_free[i]]

where square_free[i] is the highest square-free number that divides i, primes[i] is the number primes that divide i and divs[i] is the numbers that divide i.

I'm not sure about the complexity of this, but it is slightly better than the usual O(n*logn). It looks like you are doing this but you aren't grouping the numbers by their square-free factorization, so you recalculate it a lot.

there's no reason to use sieve, replace it with naive factorization

Your solution has O(T * N) complexity. Worse case will give you about 10^3 * 10^6 = 10^9 operations of multiply and divide — is not so good.

It can be seen, that there are only O(sqrt(N)) possible values of N / I and O(sqrt(M)) of M / i.

For each test you can found segments [iLeft, iRight] for M, such that

M / (iLeft - 1) > M / iLeft == M / iRight > M / (iRight + 1).

Each segment adds to answer

M / iLeft * sum(mu[iLeft] * N / iLeft, ..., mu[iRight] * N / iRight).

Complexity of this solution is O(T * (N + sqrt(M)), if we use prefix sums for mu[i] * N / i (N for recalculating prefix sums). But it is even worse, than we had at the start!

But we can use, that there are only O(sqrt(N)) possible values of N / i.

We can use segment tree, that can do next operations:

1. Set value x for each index k from [i, j];
2. Get sum of value[k] * mu[k] for k from [i, j].

We can set value N / iLeft for each segment [iLeft, iRight], such that

N / (iLeft - 1) > N / iLeft == N / iRight > N / (iRight + 1).

Complexity of this part is O(sqrt(N) * logN) and complexity of calculating answer is O(sqrt(M) * logN).

Total complexity is O(T * (sqrt(N) + sqrt(M)) * logN). Worse case will give you about 10^3 * (10^3 + 10^4) * 20 = 2 * 10^8 operations, that can be acceptable.