该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

数学课上老师讲了质数。小 Z 发现班里同学的学号两两之间有一种有趣的关系：有的学号恰好是另一个学号的「质数倍」，比如 $6$ 是 $3$ 的 $2$ 倍，$2$ 是质数。小 Z 想数一数这样的关系一共有多少对。

题目描述

本题使用文件输入输出：输入文件名为 prime.in，输出文件名为 prime.out。

给定 $n$ 个正整数 $a_1, a_2, \dots, a_n$。

如果一对下标 $(i, j)$ 满足 $i \ne j$，并且存在一个质数 $p$ 使得 $a_j = a_i \times p$，我们就称 $(i, j)$ 是一个质倍数对。

请你求出质倍数对的个数。注意 $(i, j)$ 与 $(j, i)$ 是不同的下标对。

输入格式

输入文件名为 prime.in。

第一行一个整数 $n$。

第二行 $n$ 个正整数 $a_1, a_2, \dots, a_n$，相邻两个数之间用一个空格隔开。

输出格式

输出文件名为 prime.out。

一行一个整数，表示质倍数对的个数。

样例 1 输入

5
2 4 6 3 12

样例 1 输出

5

样例 1 解释

满足条件的下标对有 $5$ 个（括号里是对应的数）：

• $(1, 2)$：$4 = 2 \times 2$；
• $(1, 3)$：$6 = 2 \times 3$；
• $(4, 3)$：$6 = 3 \times 2$；
• $(2, 5)$：$12 = 4 \times 3$；
• $(3, 5)$：$12 = 6 \times 2$。

$(1, 5)$ 不满足条件，因为 $12 = 2 \times 6$ 而 $6$ 不是质数；$(4, 5)$ 同理（$12 = 3 \times 4$）。

样例 2 输入

8
1 1 2 2 2 4 3 9

样例 2 输出

12

样例 2 解释

两个 $1$ 与三个 $2$ 之间有 $2 \times 3 = 6$ 对（$2 = 1 \times 2$）；三个 $2$ 与一个 $4$ 之间有 $3$ 对；两个 $1$ 与一个 $3$ 之间有 $2$ 对；$3$ 与 $9$ 之间有 $1$ 对。共 $6 + 3 + 2 + 1 = 12$ 对。

注意：两个相等的数不构成质倍数对（$1$ 不是质数）；$1$ 与 $4$、$1$ 与 $9$ 也不构成（$4$、$9$ 不是质数）。

样例 3

见附件 prime3.in 与 prime3.ans。

这个样例满足 $a_i \le 1000$。

样例 4

见附件 prime4.in 与 prime4.ans。

这个样例满足所有测试点的最大规模。

数据范围

对于所有测试点，保证 $1 \le n \le 2 \times 10^5$，$1 \le a_i \le 10^6$。