Количество конкатенаций палиндромов

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

namespace hash_use {
    const int H_MAXN = 1e6 + 5;
    const int p = 239017;
    int deg[H_MAXN], sum[H_MAXN];
    const int mod = 1e9 + 13;
    void init_hash() {
        deg[0] = 1;
        sum[0] = 1;
        for (int i = 1; i < H_MAXN; ++i) {
            deg[i] = (deg[i - 1] * p) % mod;
            sum[i] = deg[i];
            sum[i] += sum[i - 1];
            sum[i] %= mod;
        }
    }
    vector <int> getHash(string s) {
        vector <int> h(s.size());
        h[0] = s[0];
        for (int i = 1; i < s.size(); ++i) {
            h[i] = ((h[i - 1] * p) % mod + (s[i])) % mod;
        }
        return h;
    }
    int getHashSegment(vector <int> &hash, int l, int r) { // [0..n-1]
        int bn = ((l == 0) ? 0 : hash[l - 1]);
        int ret = (hash[r] + mod - ((bn * deg[r - l + 1]) % mod)) % mod;
        return ret;
    }
    int addHash(int hash1, int hash2, int sizehash2) {
        int ret = ((hash1 * deg[sizehash2] % mod) + hash2) % mod;
        return ret;
    }
}

vector<int> prefix_function(string s) {
    int n = (int)s.length();
    vector<int> pi(n);
    for (int i = 1; i<n; ++i) {
        int j = pi[i - 1];
        while (j > 0 && s[i] != s[j])
            j = pi[j - 1];
        if (s[i] == s[j])  ++j;
        pi[i] = j;
    }
    return pi;
}

using namespace hash_use;

string getT(string a) {
    auto get = prefix_function(a);
    int may_be = a.size() - get.back();
    bool is = 1;
    if ((a.size()) % may_be) is = 0;
    for (int i = 0; i < a.size(); ++i) {
        if (i - may_be >= 0) {
            if (a[i] != a[i - may_be]) {
                is = 0;
            }
        }
    }
    if (is) {
        return a.substr(0, may_be);
    }
    else {
        return a;
    }
}

void solve() {
    int n;
    cin >> n;
    map <string, int> T;
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        string s;
        cin >> s >> s;
        auto fx = getT(s);
        T[fx]++;
    }
    for (auto i : T) {
        ans += i.second  * i.second;
    }
    cout << ans;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    solve();
    return 0;
}