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.

The first line contains one integer $ n $ ( $ 1

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