/*
صل عل محمد
if (u == Abdel-Aziz Mostafa ) love u <3 ;
دايما احلم ربنا المنان
*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
//#define mod 998244353
#define int long long
#define F first
#define S second
string x;
int n , k;
const int N = 3e6 ;
int mod =1e9+7 , p1 ,p2 ,p3; // 19 , 17 , 256, 257 , 31
#define ll int
ll random_int(ll l , ll r){
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());
return uniform_int_distribution<ll>(l,r)(rng);
}
pair< int, pair<int,int> > Hash[N] , re_Hash[N] ;
int power(int a, int b){
if(b < 0) return 1;
int res = 1;
while(b){
if(b & 1) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
bool prime(int n) {
if (n <= 1) return false;
if (n <= 3) return true;
// Check if n is divisible by 2 or 3
if (n % 2 == 0 || n % 3 == 0) return false;
// Iterate through all numbers from 5 to the square root of n
for (int i = 5; i * i <= n; i += 6) {
if (n % i == 0 || n % (i + 2) == 0)
return false;
}
return true;
}
void pre_hash() // n * o(power) n * log
{ //zero based
// l ....r << p2 p1 p0
p1= random_int(33,300);
p2=random_int(26, 33);
p3=random_int(250,400);
mod = random_int(1e9,2e9);
int cnt = 3000 ;
while(!prime(mod) and cnt--){
mod=random_int(1e9 , 2e9);
}
if (!prime(mod))
mod= 1e9+7;
// int mod= m ;
for (int i = 0 ; i <n ; ++i){
Hash[i].F=Hash[i].S.F = Hash[i].S.S =(x[i]-'a') ;
if (i){
Hash[i].F += Hash[i-1].F*p1 ;
Hash[i].S.F += Hash[i-1].S.F*p2 ;
Hash[i].S.S += Hash[i-1].S.S*p3 ;
}
Hash[i].F%=mod;
Hash[i].S.F%=mod;
Hash[i].S.S%=mod;
}
for (int i = n-1 ; i >=0 ; --i){ // p0 p1 p2
re_Hash[i].F =re_Hash[i].S.F = re_Hash[i].S.S = x[i]-'a';
if (i!=n-1){
re_Hash[i].F +=re_Hash[i+1].F * p1;
re_Hash[i].S.F +=re_Hash[i+1].S.F *p2;
re_Hash[i].S.S +=re_Hash[i+1].S.S *p3;
}
re_Hash[i].F %=mod;
re_Hash[i].S.F%=mod;
re_Hash[i].S.S%=mod;
}
}
void lets_start_as_we_never_failed(){
}
// 2 :14
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int tc=1;
cin>>tc;
while(tc--)
lets_start_as_we_never_failed();
}
LyoKICAg2LXZhCDYudmEINmF2K3ZhdivCiAgIGlmICh1ID09IEFiZGVsLUF6aXogTW9zdGFmYSApICAgbG92ZSB1IDwzIDsKICDYr9in2YrZhdinINin2K3ZhNmFINix2KjZhtinINin2YTZhdmG2KfZhgoKKi8KI2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KI2luY2x1ZGUgPGV4dC9wYl9kcy9hc3NvY19jb250YWluZXIuaHBwPgojaW5jbHVkZSA8ZXh0L3BiX2RzL3RyZWVfcG9saWN5LmhwcD4KCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgoKLy8jZGVmaW5lIG1vZCA5OTgyNDQzNTMKI2RlZmluZSBpbnQgbG9uZyBsb25nCiNkZWZpbmUgRiBmaXJzdAojZGVmaW5lIFMgc2Vjb25kCgpzdHJpbmcgeDsKaW50IG4gICwgazsKCmNvbnN0IGludCBOICA9ICAzZTYgOwoKaW50IG1vZCA9MWU5KzcgLCBwMSAscDIgLHAzOyAgIC8vIDE5ICwgMTcgLCAyNTYsICAyNTcgICwgMzEKCgoKI2RlZmluZSBsbCBpbnQKCgpsbCByYW5kb21faW50KGxsIGwgLCBsbCByKXsKICAgIG10MTk5MzdfNjQgcm5nKGNocm9ubzo6c3lzdGVtX2Nsb2NrOjpub3coKS50aW1lX3NpbmNlX2Vwb2NoKCkuY291bnQoKSk7CiAgICByZXR1cm4gdW5pZm9ybV9pbnRfZGlzdHJpYnV0aW9uPGxsPihsLHIpKHJuZyk7Cn0KCnBhaXI8IGludCwgcGFpcjxpbnQsaW50PiA+ICBIYXNoW05dICwgcmVfSGFzaFtOXSA7CmludCBwb3dlcihpbnQgYSwgaW50IGIpewogICAgICAgIGlmKGIgPCAwKSByZXR1cm4gMTsKICAgICAgICAgaW50IHJlcyA9IDE7CiAgICAgICAgIHdoaWxlKGIpewogICAgICAgICAgICAgICAgICBpZihiICYgMSkgcmVzID0gcmVzICogYSAlIG1vZDsKICAgICAgICAgICAgICAgICAgYSA9IGEgKiBhICUgbW9kOwogICAgICAgICAgICAgICAgICBiID4+PSAxOwogICAgICAgICB9CiAgICAgICAgIHJldHVybiByZXM7Cn0KYm9vbCBwcmltZShpbnQgbikgewogICAgaWYgKG4gPD0gMSkgcmV0dXJuIGZhbHNlOwogICAgaWYgKG4gPD0gMykgcmV0dXJuIHRydWU7CgogICAgLy8gQ2hlY2sgaWYgbiBpcyBkaXZpc2libGUgYnkgMiBvciAzCiAgICBpZiAobiAlIDIgPT0gMCB8fCBuICUgMyA9PSAwKSByZXR1cm4gZmFsc2U7CgogICAgLy8gSXRlcmF0ZSB0aHJvdWdoIGFsbCBudW1iZXJzIGZyb20gNSB0byB0aGUgc3F1YXJlIHJvb3Qgb2YgbgogICAgZm9yIChpbnQgaSA9IDU7IGkgKiBpIDw9IG47IGkgKz0gNikgewogICAgICAgIGlmIChuICUgaSA9PSAwIHx8IG4gJSAoaSArIDIpID09IDApCiAgICAgICAgICAgIHJldHVybiBmYWxzZTsKICAgIH0KCiAgICByZXR1cm4gdHJ1ZTsKfQoKdm9pZCBwcmVfaGFzaCgpICAgICAgICAgICAgLy8gbiAqIG8ocG93ZXIpIG4gKiBsb2cKeyAgICAgICAgICAgICAgICAgLy96ZXJvIGJhc2VkCgogICAgICAgICAvLyAgIGwgLi4uLnIgICAgPDwgcDIgcDEgcDAKCiAgICAgICAgICAgIHAxPSAgcmFuZG9tX2ludCgzMywzMDApOwogICAgICAgICAgICBwMj1yYW5kb21faW50KDI2LCAzMyk7CiAgICAgICAgICAgIHAzPXJhbmRvbV9pbnQoMjUwLDQwMCk7CgogICAgICAgICAgICBtb2QgID0gcmFuZG9tX2ludCgxZTksMmU5KTsKCiAgICAgICAgICAgIGludCBjbnQgPSAzMDAwIDsKICAgICAgICAgICAgd2hpbGUoIXByaW1lKG1vZCkgYW5kIGNudC0tKXsKICAgICAgICAgICAgICAgICAgICBtb2Q9cmFuZG9tX2ludCgxZTkgLCAyZTkpOwogICAgICAgICAgICB9CiAgICAgICAgICAgIGlmICghcHJpbWUobW9kKSkKICAgICAgICAgICAgICAgICAgICAgbW9kPSAgMWU5Kzc7CgogICAgICAgICAvLyBpbnQgIG1vZD0gbSA7CgogICAgICAgICAgZm9yIChpbnQgaSA9IDAgOyBpIDxuIDsgKytpKXsKICAgICAgICAgICAgICAgICAgIEhhc2hbaV0uRj1IYXNoW2ldLlMuRiA9IEhhc2hbaV0uUy5TID0oeFtpXS0nYScpIDsKICAgICAgICAgICAgICAgICAgIGlmIChpKXsKICAgICAgICAgICAgICAgICAgICAgICAgICBIYXNoW2ldLkYgICArPSAgIEhhc2hbaS0xXS5GKnAxIDsKICAgICAgICAgICAgICAgICAgICAgICAgICBIYXNoW2ldLlMuRiArPSAgSGFzaFtpLTFdLlMuRipwMiA7CiAgICAgICAgICAgICAgICAgICAgICAgICAgSGFzaFtpXS5TLlMgKz0gIEhhc2hbaS0xXS5TLlMqcDMgOwogICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgICAgSGFzaFtpXS5GJT1tb2Q7CiAgICAgICAgICAgICAgICAgICBIYXNoW2ldLlMuRiU9bW9kOwogICAgICAgICAgICAgICAgICAgSGFzaFtpXS5TLlMlPW1vZDsKICAgICAgICAgIH0KICAgICAgICAgIGZvciAoaW50IGkgPSBuLTEgOyBpID49MCA7IC0taSl7ICAgICAgIC8vICBwMCBwMSBwMgogICAgICAgICAgICAgICAgICAgcmVfSGFzaFtpXS5GID1yZV9IYXNoW2ldLlMuRiA9IHJlX0hhc2hbaV0uUy5TID0geFtpXS0nYSc7CiAgICAgICAgICAgICAgICAgICBpZiAoaSE9bi0xKXsKICAgICAgICAgICAgICAgICAgICAgICAgICAgcmVfSGFzaFtpXS5GICs9cmVfSGFzaFtpKzFdLkYgKiBwMTsKICAgICAgICAgICAgICAgICAgICAgICAgICAgcmVfSGFzaFtpXS5TLkYgKz1yZV9IYXNoW2krMV0uUy5GICpwMjsKICAgICAgICAgICAgICAgICAgICAgICAgICAgcmVfSGFzaFtpXS5TLlMgKz1yZV9IYXNoW2krMV0uUy5TICpwMzsKCiAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICByZV9IYXNoW2ldLkYgJT1tb2Q7CiAgICAgICAgICAgICAgICAgICByZV9IYXNoW2ldLlMuRiU9bW9kOwogICAgICAgICAgICAgICAgICAgcmVfSGFzaFtpXS5TLlMlPW1vZDsKICAgICAgICAgIH0KfQoKdm9pZCBsZXRzX3N0YXJ0X2FzX3dlX25ldmVyX2ZhaWxlZCgpewoKCiAgICAgIAp9Ci8vIDIgOjE0CnNpZ25lZCBtYWluKCkgewoKICAgIGlvc19iYXNlOjpzeW5jX3dpdGhfc3RkaW8oMCk7CiAgICBjaW4udGllKDApOyAgICAgIGNvdXQudGllKDApOwoKICAgIGludCB0Yz0xOwogICAgY2luPj50YzsKICAgIHdoaWxlKHRjLS0pCiAgICAgICAgbGV0c19zdGFydF9hc193ZV9uZXZlcl9mYWlsZWQoKTsKCn0K