크기가 n인 수열 a₁, a₂, ..., a_n이 주어졌을 때, 1 ≤ i < j < k ≤ n 이면서, GCD(a_i, a_j, a_k) = 1인 세 쌍 (i, j, k)의 개수를 구하는 프로그램을 작성하시오. 여기서 GCD는 최대공약수를 의미한다.

입력 형식

첫째 줄에 n (1 ≤ n ≤ 10⁵)이, 둘째 줄에 a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10⁶)이 주어진다.

출력 형식

첫째 줄에 문제의 조건에 맞는 쌍의 개수를 출력한다.

예제 입력

4
1 2 3 4

예제 출력

4