Вася занимается разработкой эффективного алгоритма нахождения корня \(k\)-й степени. Неудивительно, что в скором будущем ему потребуются наборы тестовых данных.

Васин коллега Петя уже подготовил массив целых чисел \(a\). Однако, оказалось, что эти числа выбирались довольно случайно, а Васин алгоритм устроен таким образом, что успешно находит корень, лишь если он является целым числом.

Вася решил создать новый массив из таких чисел, которые будут подходить его алгоритму. Для этого он планирует использовать все такие пары \((a_i, a_j)\), что \(i < j\) и \(a_i \cdot a_j = x^k\) для какого-то целого \(k\).

Помогите Васе вычислить количество таких пар.