CF60D.Savior

Misha decided to help Pasha and Akim be friends again. He had a cunning plan — to destroy all the laughy mushrooms. He knows that the laughy mushrooms can easily burst when they laugh. Mushrooms grow on the lawns. There are a[t] mushrooms on the t-th lawn.

Misha knows that the lawns where the mushrooms grow have a unique ability. A lawn (say, i) can transfer laugh to other lawn (say, j) if there exists an integer (say, b) such, that some permutation of numbers a[i], a[j] and b is a beautiful triple (i ≠ j). A beautiful triple is such three pairwise coprime numbers x, y, z, which satisfy the following condition: _x_2 + _y_2 = _z_2.

Misha wants to know on which minimal number of lawns he should laugh for all the laughy mushrooms to burst.

米沙决定帮助帕沙和阿金重归于好。他有一个狡猾的计划——摧毁所有“爱笑蘑菇”。他知道，当这些蘑菇发笑时，它们很容易爆裂。蘑菇生长在草坪上，第 $t$ 块草坪上有 $a[t]$ 个蘑菇。

米沙知道，长有蘑菇的草坪具有一种独特能力：若存在某个整数 $b$，使得 $a[i]$、$a[j]$ 和 $b$ 的某种排列构成一个“优美三元组”（其中 $i \ne j$），则第 $i$ 块草坪便可将笑声传递给第 $j$ 块草坪。“优美三元组”是指三个两两互质的正整数 $x, y, z$，满足如下条件：

$$x^2 + y^2 = z^2.$$

米沙想知道：他至少需要在多少块草坪上发笑，才能使所有爱笑蘑菇全部爆裂？

The first line contains one integer n (1 ≤ n ≤ 106) which is the number of lawns. The next line contains n integers a__i which are the number of mushrooms on the i-lawn (1 ≤ a__i ≤ 107). All the numbers are different.

第一行包含一个整数 $n$（$1 \leq n \leq 10^6$），表示草坪的数量。
下一行包含 $n$ 个整数 $a_i$，表示第 $i$ 块草坪上的蘑菇数量（$1 \leq a_i \leq 10^7$）。所有数字互不相同。

Print a single number — the minimal number of lawns on which Misha should laugh for all the mushrooms to burst.

输出一个整数——米沙需要在上面发笑的最少草坪数量，使得所有蘑菇都爆裂。