GCD 쌍

모든 도형이 의식을 가진 존재인 Shape Galaxy에서 원과 정사각형이 반목하고 있다. 원은 모든 경로가 평평하기를 원하고, 정사각형은 일정한 간격으로 배치된 역현수선 모양의 언덕이어야 한다고 주장한다. 이 반목 때문에 원은 제곱 편향 수를 싫어하기 시작했다. 정수 $s$가 어떤 정수 $x > 1$에 대해 $x^2$으로 나누어떨어지면 $s$는 제곱 편향 수이다.

Mr. Circle은 배열에 있는 모든 수 쌍의 최대공약수를 계산하는 과제를 맡았다. 그는 한 걸음 더 나아가 제곱 편향 수가 아닌 최대공약수의 개수를 세려고 한다.

첫 줄에 배열의 길이를 나타내는 정수 $n$ $(1 \le n \le 10^5)$이 주어진다.

이어지는 $n$개의 줄에는 배열의 원소인 정수 $a_i$ $(1 \le a_i \le 10^{12})$가 한 줄에 하나씩 주어진다.

$\gcd(a_i, a_j)$가 제곱 편향 수가 아닌 쌍 $(i, j)$ $(1 \le i < j \le n)$의 개수를 하나의 정수로 출력한다.