Background

Special for beginners, ^_^

Description

徐老师的队伍去区域赛取得了不错的成绩，拿到了银牌，徐老师决定犒赏一下。 他带学生来到一家戈壁滩，这家的羊肉串，每串都有一个序列号 $（\le10^{11}）$，三名队员可以自主选择羊肉串。如果最终被徐老师发现有其中两串羊肉串的序列号相乘是一个完全平方数，那么这顿饭就大家AA，如果找不到，就徐老师买单。 请问给出每串羊肉串的序列号，在这个游戏规则下，三人最多能白嫖到多少串羊肉串？

Format

Input

第一行一个整数n表示数组长度 第二行n个正整数表示所有可供挑选的羊肉串的序列号。 .

Output

一个整数表示最多能白嫖的羊肉串数量。

Samples

5
1 1 2 3 4

3

7
1 3 2 5 4 9 1

4

Limitation

1s, 1024KiB for each test case.