#include <bits/stdc++.h> #define nl 1000007 #define bg_NUM 1000000009 #define fi first #define se second #define sz() size() #define ll long long #define ps push_back #define pii pair<int,int> //#define int long long using namespace std; mt19937_64 rd(time(0)); long long Random( long long l , long long r ) { return l + rd() % (r-l+1) ; } int T; vector<string> S; int n; ll hs[5][nl], pw[5][nl]; ll base[5] = { 113, 317, 77, 101 }; ll mod[5] = { 1092009103, 1312323217, 727313771, 919191309 }; pair<pair<ll,ll>,pair<ll,ll>> get( int l, int r ) { return { {(((hs[0][r] - hs[0][l-1] + mod[0]*mod[0]) % mod[0]) * pw[0][n-r]) % mod[0], (((hs[1][r] - hs[1][l-1] + mod[1]*mod[1]) % mod[1]) * pw[1][n-r]) % mod[1]}, {(((hs[2][r] - hs[2][l-1] + mod[2]*mod[2]) % mod[2]) * pw[2][n-r]) % mod[2], (((hs[3][r] - hs[3][l-1] + mod[3]*mod[3]) % mod[3]) * pw[3][n-r]) % mod[3]} }; } //pair<ll,ll> get( int l, int r ) { // // return { // // (((hs[0][r] - hs[0][l-1] + mod[0]*mod[0]) % mod[0]) * pw[0][n-r]) % mod[0], // (((hs[1][r] - hs[1][l-1] + mod[1]*mod[1]) % mod[1]) * pw[1][n-r]) % mod[1] // }; //} void Solve( string &s ) { n = s.sz(); s = " " + s; for( int tp = 0 ; tp < 2 ; tp ++ ) { hs[tp][0] = 0; for( int i = 1 ; i <= n ; i ++ ) hs[tp][i] = (hs[tp][i-1] + 1ll*(s[i]-'a'+1)*pw[tp][i-1]) % mod[tp]; } int cnt = 0, i = 1, r = n; while(1) { int res = -1; for( int len = 1 ; len <= (r-i+1)/2 ; len ++ ) { if(get(i,i+len-1) == get(r-len+1,r)) { res = len; cnt += 2; break; } } if(res < 0) { if(i <= r)cnt ++; break; } i += res; r -= res; } cout << cnt << '\n'; } void Process() { for( int i = 1 ; i <= T ; i ++ ) Solve(S[i]); } void Test() { ofstream out("SIXCUP.inp"); int Ntest = 20; out << Ntest << '\n'; while(Ntest --) { int sz = Random(5000,70000); while(sz--) out << char(Random('a','z')); out <<'\n'; } } int main() { #define Beta "SIXCUP" if( fopen( Beta ".INP", "r" ) ){ freopen( Beta ".INP", "r", stdin ) ; freopen( Beta ".OUT", "w", stdout ) ; } ios_base::sync_with_stdio(false); cin.tie(nullptr); //Test(); cin >> T; S.resize(T+1); for( int i = 1 ; i <= T ; i ++ ) cin >> S[i]; for( int tp = 0 ; tp < 2 ; tp ++ ) { pw[tp][0] = 1; for( int i = 1 ; i <= nl-7 ; i ++ ) pw[tp][i] = (pw[tp][i-1]*base[tp])%mod[tp]; } Process(); } /* NHO XOA COMMENT !!! 4 gspvhcute anhanh anhhanh diduadudi */

palindromic.cpp: In function 'int main()':
palindromic.cpp:123:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  123 |         freopen( Beta ".INP", "r", stdin )  ;
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
palindromic.cpp:124:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  124 |         freopen( Beta ".OUT", "w", stdout ) ;
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~