小红有一个长度为 的整数数组 ，如果从数组中任选两个数 ，他们的乘积都是完全平方数，那么这个数组就是好数组。 如果现在的数组不是一个好数组，小红可以执行任意多次操作： 从数组里选择一个数，将其乘以一个正整数 ； 她想知道，最少需要多少次操作才能使数组变成好数组。 如果一个数可以被表示为一个整数的平方，那么这个数就是完全平方数。

输入描述:

第一行输入一个整数  代表数组中元素的数量。第二行输入  个整数  代表数组中的元素。

输出描述:

在一行上输出一个整数，代表最少需要的操作次数。