Problem11378--洛谷P2714 - 四元组统计

11378: 洛谷P2714 - 四元组统计

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 512 MiB

Description

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

Input

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

Output

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

Constraints

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

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

Sample 1 Input

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

Sample 1 Output

1
0
34

HINT

洛谷P2714.

Source/Category