#include <bits/stdc++.h>
using namespace std;

int prime[100001] = {0};
int k[100001] = {0};

void Sieve() {
    for (int i = 1; i < 100001; i++)
        k[i] = i;

    for (int i = 2; i < 100001; i++) {
        if (prime[i] == 0) {
            for (int j = i; j < 100001; j += i) {
                prime[j] = 1;
                while (k[j] % (i * i) == 0)
                    k[j] /= (i * i);
            }
        }
    }
}

int countPairs(int arr[], int n) {
    unordered_map<int, int> freq;
    for (int i = 0; i < n; i++) {
        freq[k[arr[i]]]++;
    }

    int sum = 0;
    for (auto i : freq) {
        sum += ((i.second - 1) * i.second) / 2;
    }

    return sum;
}