Description

There are $n$ positive integers $a _ i$. You need to count how many quadruples satisfy $\gcd(a _ i, a _ j, a _ k, a _ l) = 1$.

Input Format

The input contains multiple testdata sets. For each testdata set: the first line contains a positive integer $n$, followed by one line with $n$ positive integers $a _ i$.

Output Format

Several lines, each corresponding to one testdata set, representing the number of quadruples that satisfy the requirement.

4
2 3 4 5
4
2 4 6 8
7
2 3 4 5 7 6 8  

1
0
34

Hint

For $30\%$ of the testdata, $4 \le n \le 10$, and the number of testdata sets does not exceed $10$.

For $100\%$ of the testdata, $4 \le n \le 10000$, $1 \le a _ i \le 10000$, and the number of testdata sets does not exceed $100$.

Translated by ChatGPT 5