i need to solve this equation efficiently

m+n-gcd(m,n)=N

i.e, when N is given i need to find NUMBER OF PAIRS of m,n that satisify the equation

N<10^6

can any 1 help !!!