Note that . Therefore one of a or b must be divisible by , and one of a or b must be divisible by . How many ordered pairs (a,b) satisfy these conditions?

This method definitely generalizes, but I doubt there is a general formula since it becomes one giant counting problem when N has more prime divisors.