四元组统计

题目背景

有n个正整数ai,你要统计有多少个四元组满足gcd(ai,aj,ak,al) = 1。

题目描述

输入输出格式

输入格式


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

输出格式


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

输入输出样例

输入样例 #1

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

输出样例 #1

1
0
34

说明

对于 30%的数据,4 ≤ n ≤ 10,且数据组数不超过 10; 对于 100%的数据,4 ≤ n ≤ 10000,1 ≤ ai≤ 10000,且数据组数不超过100