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.

Input

The first line contains one integer $*n*$ ($1 ≤ *n* ≤ 10^{6}$) 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*} ≤ 10^{7}$). All the numbers are different.

Output

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