D. Спаситель
ограничение по времени на тест
4 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

Миша решил помочь Паше и Акиму помириться. У него есть хитрый план — уничтожить все смешливые грибы. Он знает, что смешливые грибы замечательно лопаются от смеха. На полянках растут грибы. На t-ой полянке растет a[t] грибов.

Ещё Миша знает, что у полянок, на которых растут грибы, есть уникальная способность. Полянка (например, i) может передать свой смех на другую полянку (например, j) если существует целое число (например, b) такое, что некоторая перестановка чисел a[i], a[j] и b является красивой тройкой (i ≠ j). Красивая тройка — это такие три попарно взаимно простые числа x, y, z, что: x2 + y2 = z2.

Миша хочет узнать, на каком минимальном количестве полянок ему нужно посмеяться, чтобы все смешливые грибы лопнули.

Входные данные

В первой строке находится одно целое число n (1 ≤ n ≤ 106) — количество полянок. В следующей строке содержится n целых чисел ai — количество грибов на полянке (1 ≤ ai ≤ 107). Все количества различны.

Выходные данные

Выведите одно число — минимальное количество полянок, на которых Миша должен посмеяться, чтобы все грибы лопнули.

Примеры
Входные данные
1
2
Выходные данные
1
Входные данные
2
1 2
Выходные данные
2
Входные данные
2
3 5
Выходные данные
1