Misha 决定帮助 Pasha 和 Akim 再次成为朋友。他有一个狡猾的计划——消灭所有的笑蘑菇。他知道笑蘑菇笑起来很容易爆裂。草坪上长出了蘑菇。第 t 个草坪上有一个蘑菇。
米莎知道,蘑菇生长的草坪有着独特的能力。如果存在一个整数(例如,b),使得数字 a[i]、a[j] 和 b 的某些排列是一个美丽的三元组(i ≠ j),则草坪(例如,i)可以将笑声转移到其他草坪(例如,j)。一个美丽的三元组是这样三个成对的互质数 x, y, z,满足以下条件:x2 + y2 = z2。
Misha 想知道他应该在多少块草坪上笑才能让所有笑蘑菇爆裂。
输入
第一行包含一个整数 n (1 ≤ n ≤ 106),它是草坪的数量。下一行包含 n 个整数 ai,它们是第 i-草坪上蘑菇的数量 (1 ≤ ai ≤ 107)。所有数字都不同。
输出
打印一个数字——米莎应该笑到所有蘑菇爆裂的最小草坪数量。
示例
输入 #1
1 2
输出 #1
1
输入 #2
2 1 2
输出 #2
2
输入 #3
2 3 5
输出 #3
1