Вы сидите на вершине дерева с небольшой командой выживших в центре бобро-зомби апокалипсиса.
На земле вас окружили N бобров-зомби, которые вот-вот сточат ствол дерева!
У каждого бобра-зомби есть свой размер si, выраженный натуральным числом.
Учёный, который недавно погиб от несчастного случая, рассказал, что, если стравить двух бобров-зомби между собой с помощью особых радиоволн, то они образуют могущественного Бобротрона, размер которого будет равен произведению размеров стравленных бобров.
Последними словами учёного было уточнение, что если размер Бобротрона будет квадратом целого числа, то он будет на вашей стороне, вселит ужас в остальных бобров-зомби и заставит их убежать!
Срочно посчитайте, сколькими способами можно создать доброго Бобротрона, стравливая двух бобров-зомби!
Первая строка ввода содержит целое число N — количество бобров-зомби (2 ≤ N ≤ 200 000).
Вторая строка содержит N целых чисел si, разделённых пробелами — размеры бобров-зомби (1 ≤ si ≤ 200 000).
Выведите количество пар бобров, которые смогут образовать доброго Бобротрона.
4
1 4 9 16
6
4
2 4 6 8
1
В первом примере подойдёт любая пара бобров.
Во втором примере подойдёт лишь пара бобров с размерами 2 и 8.