Со одлука на Министерството за образование, најголемиот и најдобриот факултет во Македонија, Факултетот за информатички науки и компјутерско инженерство, треба да добие нова зграда. Пред да се започне со изградба на зградата, потребно е да се одбере кој ќе ја гради истата, и како таа ќе изгледа. За таа цел, факултетот одлучил да направи тендер на кој може да учествуваат повеќе компании.

Бидејќи професорите на ФИНКИ се (малку) чудни луѓе (кои се опседнати со цели броеви, прави агли, правоаголни триаголници и слично), тие одлучиле наместо да гласаат за најдобрата компанија/проект, да објават интересен предизвик за решавање, и за победник на тендерот да ја прогласат компанијата која прва ќе успее да го реши.

Предизвикот е објаснет во продолжение:

• Дадени се неколку позитивни цели броеви A1, A2, A3, ..., An, кои ги означуваат должините на прегради кои може да се искористат за изградба на некој објект.
• Кои било две прегради со должини X и Y од погорната листа може да се спојат меѓусебно и да се изгради ѕид доколку се исполнети следните два услови:
• • X и Y немаат заеднички делител - т.е. НЗД(X, Y) = 1, и
  • постои позитивен цел број Z, така што (X, Y, Z) може да претставуваат страни на правоаголен триаголник каде Z е хипотенузата (најдолгата страна). Со други зборови, постои цел број Z така што X^2 + Y^2 = Z^2. (Како што кажавме, професорите се опседнати со цели броеви и прави агли.)
• Нормално, секоја преграда може да се искористи најмногу еднаш (откако две прегради ќе се спојат во ѕид, тие се бришат од листата на расположливи прегради). Кој е максималниот број на прегради од листата кои може да се искористат при градбата?

Петар е сопственик на една компанија која сака да учествува на тендерот. Можете ли да му помогнете на Петар и да напишете програма која ќе го реши предизвикот – односно, која ќе успее да го најде бараниот максимален број на прегради кои може да се искористат?

Влез

Во првиот ред е запишан еден цел број N (1 <= N <= 150), кој го означува бројот на прегради. Во вториот ред се запишани N цели броеви Ai (1 <= Ai <= 1 000 000), кои ги означуваат должините на преградите.

Во тест случаи кои вредат најмалку 30% од поените, ќе важи (1 <= N <= 9) и (1 <= Ai <= 100)

Излез

Отпечатете го бараниот максимален број на прегради.

Ограничувања

Временско ограничување: 1 second
Мемориско ограничување: 64 megabytes

Примери

влез
3   
3 4 4

излез
2

влез
7
40 33 9 56 9 40 2

излез
6

влез
2
3 5

излез
0

Објаснување за првиот пример: Може да се искористат 2 прегради од листата (со должини 3 и 4), бидејќи НЗД(3, 4) = 1 и 3^2+4^2=5^2. Секоја преграда може да се искористи најмногу еднаш, па не може да се направат два пара (3, 4) и (3, 4) бидејќи имаме само една преграда со должина 3.

Објаснување за вториот пример: Паровите се (9, 40), (9, 40) и (33, 56). Вкупно се искористија 6 прегради од листата, па точниот одговор е 6.

Објаснување за третиот пример: Одговорот е 0. Иако НЗД(3, 5) = 1, не е исполнет вториот услов – т.е., не постои ЦЕЛ позитивен број Z, така што 3^2+5^2=Z^2.