시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 47 23 16 42.105%

문제

크기가 n인 수열 a1, a2, ..., an이 주어졌을 때, 1 ≤ i < j < k ≤ n 이면서, GCD(ai, aj, ak) = 1인 세 쌍 (i, j, k)의 개수를 구하는 프로그램을 작성하시오. 여기서 GCD는 최대공약수를 의미한다.

입력

첫째 줄에 n (1 ≤ n ≤ 105)이, 둘째 줄에 a1, a2, ..., an (1 ≤ ai ≤ 106)이 주어진다.

출력

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

예제 입력 1

4
1 2 3 4

예제 출력 1

4

힌트

출처