Problem2150--编年数

2150: 编年数

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 136  Solved: 64
[Status] [Submit] [Creator:]

Description

如果一个整数可以表示成一个质数的次方,则我们称这个数为”编年数”。比如:

· 7 是编年数,因为 7 = 71
· 16 是编年数,因为 16 = 24
· 125 是编年数,因为 125 = 53
· 243 是编年数,因为 243 = 35

而:
· 6 不是编年数,因为 6 = 2 × 3
· 100 不是编年数,因为 100 = 22 × 52
· 162 不是编年数,因为 162 = 2 × 34

特殊地,1 也是编年数,因为 1 可以表示成任何一个正整数的 0 次方。

现在给你 n 个整数,请你判断这 n 个整数中有多少个编年数。

Input

第一行,一个整数 n(1 ≤ n ≤ 100)。
第二行,n 个整数,两两之间以一个空格分隔,每个整数均为不超过 106 的正整数。

Output

输出一个整数,表示编年数的个数。

Sample Input Copy

5
9 13 100 81 49

Sample Output Copy

4

Source/Category