Diagonal Enumeration

You certainly know of this nice proof of the equipotence between the set of integers and the set of rational numbers.

We consider an infinite grid numbered horizontally and vertically with integers:

We run through this grid according the above pattern and count each pair (i,j) where i and j are coprime.

We obtain the following bijection:

1 - $\frac{1}{1}=1$

2 - $\frac{1}{2}$
3 - $\frac{2}{1}=2$

4 - $\frac{3}{1}=3$
5 - $\frac{1}{3}$

6 - $\frac{1}{4}$
7 - $\frac{2}{3}$
8 - $\frac{3}{2}$
9 - $\frac{4}{3}$

10 - $\frac{5}{1}=5$
11 - $\frac{1}{5}$

12 - $\frac{1}{6}$
13 - $\frac{2}{5}$
14 - $\frac{3}{4}$
15 - $\frac{4}{1}=4$
16 - $\frac{5}{2}$
17 - $\frac{6}{1}=6$

If we run through the upper diagonal matrix of a $6\times 6$ grid, we get 17 rationals.

How many rationals can we count in the upper diagonal matrix of a ${10}^9\times {10}^9$ grid?

You are given: 303964542391 for a ${10}^6\times {10}^6$ grid
[My timing: < 90 sec]