有一天,Kira 找到了来自 Morioh 的 $$$n$$$ 朋友,并决定将他们聚集在一张桌子旁进行和平对话。好友 $$$i$$$ 的身高等于 $$$a_i$$$。碰巧的是,每个朋友的身高都是独一无二的。
不幸的是,Kira 家里只有 $$$3$$$ 椅子,显然不可能让所有朋友都坐下!因此,Kira 仅需邀请 $$$3$$$ 的朋友。
但是一切并没有那么简单!如果邀请的朋友中最低的和最高的身高不互质,那么朋友们就会互相捉弄,这会极大地激怒基拉。
Kira开始感兴趣了,有多少种方法可以选择他的朋友$$$3$$$,这样他们就不会耍花招了?如果有朋友以一种方式被邀请,但没有以另一种方式被邀请,则两种方式被认为是不同的。
正式来说,如果 Kira 邀请好友 $$$i$$$、$$$j$$$ 和 $$$k$$$,则应满足以下条件:$$$\gcd(\min(a_i, a_j, a_k), \max(a_i, a_j, a_k)) = 1$$$,其中 $$$\gcd(x, y)$$$ 表示数字 $$$x$$$ 和 $$$y$$$ 的最大公约数 (GCD)。
Kira 的计算机科学不是很强,所以他要求你数一下邀请好友的方式。
输入
第一行包含数字 $$$n$$$ ($$$3 \le n \le 3\cdot10^5$$$) — Kira 的朋友数量。
下一行包含 $$$n$$$ 不同的整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 3\cdot10^5$$$) — Kira 朋友的身高。
输出
在一行中输出邀请三位好友的方法数量。
示例
输入 #1
3 1 2 3
输出 #1
1
输入 #2
4 1 6 2 3
输出 #2
3
输入 #3
4 16 4 8 2
输出 #3
0
输入#4
10 10 1 6 7 9 8 4 3 5 2
输出#4
77
注意
在第一个示例中,只有一种方式适合:邀请好友 $$$1$$$、$$$2$$$ 和 $$$3$$$。这里 $$$1 < 2 < 3$$$,数字 $$$1$$$ 和 $$$3$$$ 是互质的。