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

小希想要的完全平方数

题目描述

虽然春节已经结束了，但我们的小希还在打扫房间。 今天收拾出了一堆数，她想用 乘积的方式 把它们合成一个完全平方数放在保险柜里，但她不确定这些数能不能变成完全平方数。 所以想请你帮帮她，添一些数使得这组数一定可以变成完全平方数。已知增添一个数 $m$ 需要花费 $m$ 点魔力，求 最少 需要多少魔力（增添的数至少为 $1$，虽然加 $1$ 也没什么意义就是了）。

输入描述：

第一行一个 $n\left(1 \leqq n \leqq 2 \times 10^5 \right)$ 表示数组的长度。

第二行输入 $n$ 个数，每个数$x\left(1 \leqq x \leqq 1 \times 10^5 \right)$。

输出描述：

输出一个数 $n$ 表示一共花费了 $n$ 点魔力。

示例1

输入

1
9

输出

0

示例2

输入

3
9 7 21

输出

3