Count coprime pairs

Given an integer n (1 <= n <= 100000), count the number of unordered pairs (i, j) with 1 <= i < j <= n such that gcd(i, j) == 1 (i and j are coprime). For example, for n = 5 there are 9 coprime pairs. A naive O(n^2) gcd over all pairs is too slow at the upper bound.