HOME_W的头顶好凉啊

给定n个整数a₁,a₂,a₃……a_n，且1<=a_i<=n问有多少对i,j 满足i<j   且gcd(a[i],a[j])=1,2,3,……n。

单组数据

第一行包含一个整数n。

接下一行有n个整数 a1,a2,a3……an

1<=ai<=n

1<=n<=10⁵

输出n行，每行包含一个整数，第k行代表gcd(a[i],a[j])=k的方案数

10
1 1 1 1 1 1 1 1 1 1

45
0
0
0
0
0
0
0
0
0