Quadruple GCD 1 Count

You are given n positive integers \(a_i\). Your task is to count the number of quadruples \((i, j, k, l)\) (with \(i<j<k<l\)) such that \(\gcd(a_i, a_j, a_k, a_l) = 1\).

Note: A quadruple consists of 4 distinct indices chosen in increasing order, and \(\gcd(\cdot)\) denotes the greatest common divisor.

inputFormat

The first line contains an integer \(n\) (the number of elements). The second line contains \(n\) positive integers \(a_1, a_2, \dots, a_n\) separated by spaces.

outputFormat

Output a single integer representing the number of quadruples \((i, j, k, l)\) such that \(\gcd(a_i, a_j, a_k, a_l) = 1\).

sample

4
1 1 1 1

1