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

题目背景

昆明菌子极多。雨季逛菜市场，随时可以看到各种菌子。最多，也最便宜的是牛肝菌。牛肝菌下来的时候，家家饭馆卖炒牛肝菌，连西南联大食堂的桌子上都可以有一碗。牛肝菌色如牛肝，滑，嫩，鲜，香，很好吃。炒牛肝菌须多放蒜，否则容易使人晕倒。青头菌比牛肝菌略贵。这种菌子炒熟了也还是浅绿色的，格调比牛肝菌高。菌中之王是鸡 ，味道鲜浓，无可方比。鸡 是名贵的山珍，但并不真的贵得惊人。一盘红烧鸡 的价钱和一碗黄焖鸡不相上下，因为这东西在云南并不难得。有一个笑话：有人从昆明坐火车到呈贡，在车上看到地上有一棵鸡 ，他跳下去把鸡 捡了，紧赶两步，还能爬上火车。这笑话用意在说明昆明到呈贡的火车之慢，但也说明鸡 随处可见。有一种菌子，中吃不中看，叫作干巴菌。乍一看那样子，真叫人怀疑：这种东西也能吃?!颜色深褐带绿，有点像一堆半干的牛粪或一个被踩破了的马蜂窝。里头还有许多草茎、松毛，乱七八糟!可是下点功夫，把草茎松毛择净，撕成蟹腿肉粗细的丝，和青辣椒同炒，入口便会使你张目结舌：这东西这么好吃?!还有一种菌子，中看不中吃，叫鸡油菌。都是一般大小，有一块银圆那样大，滴溜儿圆，颜色浅黄，恰似鸡油一样。这种菌子只能做菜时配色用，没甚味道。

题目描述

这一天 $wqsing$ 采集了 $n$ 个菌子，编号为 $1, 2, 3, ... ,n$，每个菌子的特色值为 $a_i$。

现在 $wqsing$ 想要用这些菌子制作几顿菌子火锅。对于每顿菌子火锅，菌子火锅的初始美味值为 $1$，如果我们加入第 $k$ 个菌子，美味值 $val$ 就会变为原来的 $a_k$ 倍。注意：每个菌子只能使用一次，每顿菌子火锅必须包含至少 $1$ 个菌子。

$atzk$ 非常喜欢美味值为完全平方数的菌子火锅，请问 $atzk$ 最多能吃到多少顿美味值为完全平方数的菌子火锅。

输入格式

前一行 $1$ 个数 $n$ 。

接下来一行输入 $a_1, a_2, a_3, ... , a_n$

输出格式

一个整数，表示 $atzk$ 最多能吃到多少顿美味值为完全平方数的菌子火锅

样例 #1

样例输入 #1

5
1 6 8 3 4

样例输出 #1

3

样例 #2

样例输入 #2

5
22 24 15 77 35

样例输出 #2

1

样例 #3

样例输入 #3

16
9797 8633 7387 6557 5767 5183 4757 4087 3599 3127 2491 2021 1763 1517 1147 3131

样例输出 #3

1

提示

对于 $100\%$ 数据 $2 \le n \le 16, 1 \le a_i \le 10000$。