Problem Description

题目描述

有 $n$ 个正整数 $a _ i$，你要统计有多少个四元组 $(i,j,k,l)$ 满足 $i<j<k<l$ 且 $\gcd(a_i,a_j,a_k,a_l) = 1$。

输入格式

输入包含多组数据。
对于每组数据：第一行一个正整数 $n$，接下来一行 $n$ 个正整数 $a _ i$。

输出格式

若干行，每行对应一个输入数据，表示满足要求的四元组的个数。

样例

样例 1

提示

对于 $30\%$ 的数据，$4 ≤ n ≤ 10$，且数据组数不超过 $10$；

对于 $100\%$ 的数据，$4 ≤ n ≤ 10000$，$1 ≤ a _ i≤ 10000$，且数据组数不超过 $100$。

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

1
0
34