Let's solve the problem for each prime factor p separately.

Suppose LCM of two numbers i and j has p^e in its factorization, then at least one of them must have p^e in its factorization as well. There are (e + 1)² - e² ways to choose the exponents of p so that one of the numbers has exponent e and the other one has exponent at most e.

First let's make a list of primes with a sieve, then solve the problem for each prime factor as explained above. The results have to be multiplied because each prime factor is independent.

We'll be counting all pairs twice, except the case when i = j (when n is a perfect square), so if the answer calculated is res then will do the trick.