题目描述

在童话森林的深处，住着各种会魔法的小动物。每只小动物的魔法能量由一颗 “魔法石” 储存，石头上刻着 $1$ 到 $5*10^5$ 之间的神秘符文。动物王国有一个古老的传说：只有当两只小动物的魔法符文相乘的结果是一个质数时，它们才会成为 “心灵伙伴”，共享魔法力量；否则就算住在同一个树洞里，也只能算是 “森林中的过客”。

森林长老树精灵希望知道，整个王国里有多少对 “森林过客”，以便准备今年友谊节的礼物数量。

输入格式

第一行一个整数 $n$，表示小动物的数量。

第二行 $n$ 个整数，表示每只小动物的魔法符文。

输出格式

输出一个整数，表示 “森林过客” 的对数。

样例

5  
1 2 3 4 5

7

4
1 1 2 3

2

数据范围

对于 $30\%$ 的数据，$1 \le n \le 1000$。

对于 $100\%$ 的数据，$1 \le n \le 5\times10^5$。