问题背景

在盛大的阅兵仪式中，$n$个士兵方阵依次通过主席台。每个方阵的士兵人数为一个正整数。阅兵指挥部规定：当一个方阵通过主席台时，如果该方阵及其之前所有方阵的士兵总人数是一个完全平方数，那么这次通过就被称为一次"完美通过"。

请你计算，在整个阅兵过程中，总共有多少次完美通过？

输入格式

第一行包含一个整数$n$，表示方阵的数量。

第二行包含$n$个正整数$a_1, a_2, ..., a_n$，表示每个方阵的士兵人数。

输出格式

输出一个整数，表示完美通过的总次数。

样例

5
1 3 5 7 9

5

6
2 2 2 2 2 2

1

4
16 9 25 36

2

数据范围

• 60% 的数据：$n \leq 1000$，$a \leq 1000$。
• 80% 的数据：$n \leq 1000$，$a \leq 10^6$。
• 100% 的数据：$n \leq 50000$，$a \leq 10^6$。