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