서로소인 수

두 양의 정수의 공약수가 $1$뿐일 때, 두 수를 서로소라고 한다. 양의 정수로 이루어진 수열 $a_1, a_2, \dots, a_n$이 주어질 때, 이 수열의 항들 중에서 서로소인 쌍의 개수를 구하여라.

첫째 줄에 수열의 길이 $n$ ($1 \le n \le 10^6$)이 주어진다. 둘째 줄에 $n$개의 정수 $a_i$ ($1 \le a_i \le 3 \times 10^6$)가 공백으로 구분되어 주어진다.

$1 \le i < j \le n$이면서 $a_i$와 $a_j$가 서로소인 쌍 $(i, j)$의 개수를 정수 하나로 출력한다.