b.cpp

#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define ll long long

#define IOS ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

using namespace std;
const int INF = 1e9 + 10;
const int MOD = 1e9 + 7;
const int MOD2 = 1e9 + 9;
const int MAXN = 2e6 + 10;
int arr[MAXN];

pair <ll, ll> get_hash1(int l, int r){
    return {(hash1[r] - hash1[l - 1] + MOD1) * st1[n - l] % MOD1,
            (hash2[r] - hash2[l - 1] + MOD2) * st2[n - l] % MOD2};
}
pair <ll, ll> get_hash2(int l, int r){
    return {(hash3[l] - hash3[r + 1] + MOD1) * st1[r - 1] % MOD1,
            (hash4[l] - hash4[r + 1] + MOD2) * st2[r - 1] % MOD2};
}

bool check(int l, int r){
    return (get_hash1(l, r) == get_hash2(l, r));
}
void solve(){

    string s;
    cin >> s;

    int n = s.size();
    s = "#" + s;
    st1[0] = 1;
    for (int i = 1; i <= n; i++){
        st1[i] = (st1[i - 1] * p1) % MOD1;
        st2[i] = (st2[i - 1] * p2) % MOD2;
    }
    for (int i = 1; i <= n; i++){
        hash1[i] = (hash1[i - 1] + st1[i] * (s[i] - 'a' + 1)) % MOD1;
        hash2[i] = (hash2[i - 1] + st2[i] * (s[i] - 'a' + 1)) % MOD2;
    }
    for (int i = n, j = 1; i >= 1; i--, j++){
        hash3[i] = (hash3[i + 1] + st1[j] * (s[i] - 'a' + 1)) % MOD1;
        hash4[i] = (hash4[i + 1] + st2[j] * (s[i] - 'a' + 1)) % MOD2;
    }

    ...


    ...


    cout << ans << "\n";


}

int main() {
    IOS;
    int t = 1;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}