Дан массив целых положительных чисел a1,a2,…,an. Требуется определить количество пар (i,j) (1≤i<j≤n), таких что произведение чисел ai⋅aj является кубом какого-либо целого числа.
Входные данные
Первая строка содержит одно целое число n (1≤n≤105) — количество элементов в массиве.
Вторая строка содержит n целых чисел a1,a2,…,an (1≤ai≤109) — элементы массива.
Выходные данные
Выведите ответ на задачу.
Система оценки
Тест 1: Пример из условия.
Тесты 2-3: n,ai≤100
Тесты 4-5: ai≤100.
Тесты 6-10: без дополнительных ограничений.
Примечание
Все подходящие пары (i,j):
(1, 4): a1⋅a4=27=33
(1, 5): ai⋅a5=8=23
(2, 3): a2⋅a3=216=63
(4, 5): a4⋅a5=216=63.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1 4 54 27 8
|
4
|