题目描述

Stancu 喜欢太空旅行，但作为贫穷的开发者，他打算偷 Petru 的宇宙飞船。飞船被一个基于银河系恒星 $ID$ 号的密码系统锁定，破解系统需要检查所有四元组恒星子集，要求它们的唯一公约数（$GCD$）为 $1$。给定 $N$ 颗恒星的 $ID$ 列表，求满足条件的四元组子集数目。

输入格式

• 每个测试用例首行是整数 $N$（$1 ≤ N ≤ 10000$）。
• 第二行是 $N$ 个正整数（$ID 号 ≤ 10000$），用空格分隔。
• 输入以文件结束符终止。

输出格式

对每个测试用例，输出满足条件的四元组数目，占一行。

输入输出样例

输入数据 1

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

输出数据 1

1  
0  
34  

来源

$2008$ 年东南欧地区程序设计竞赛