# 題目大意

• 將當前串翻轉後接到原串中
• 在當前串首或串尾加入一個字元

Data Constraint

# SRC

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std ;
#define N 100000   10
struct Tree {
int Son[4] ;
int cost , len , fail ;
} T[N] ;
char S[N] ;
int Tab[N] ;
int Test , Last , L , tot , ans ;
int Find( int now , int half ) {
while ( T[now].len > half ) now = T[now].fail ;
return now ;
}
int Getfail( int now ) {
while ( S[L-T[now].len-1] != S[L] ) now = T[now].fail ;
return now ;
}
void ADD( int c ) {
L    ;
int now = Getfail( Last ) ;
if ( !T[now].Son[c] ) {
T[  tot].fail = T[Getfail(T[now].fail)].Son[c] ;
T[now].Son[c] = tot ;
T[tot].len = T[now].len   2 ;
if ( (T[tot].len & 1) == 0 ) {
int j = Find( T[tot].fail , T[tot].len / 2 ) ;
T[tot].cost = min( T[now].cost   1 , T[j].cost   T[tot].len / 2 - T[j].len   1 ) ;
} else T[tot].cost = T[tot].len ;
}
Last = T[now].Son[c] ;
}
int main() {
freopen( "gene.in" , "r" , stdin ) ;
freopen( "gene.out" , "w" , stdout ) ;
scanf( "%d" , &Test ) ;
Tab['A'] = 0 , Tab['C'] = 1 , Tab['G'] = 2 , Tab['T'] = 3 ;
while ( Test -- ) {
memset( T , 0 , sizeof(T) ) ;
T[0].fail = T[0].cost = 1 ;
T[1].len = -1 , T[1].cost = 2 ;
Last = S[0] = 0 ;
tot = 1 , L = 0 ;
scanf( "%s" , S   1 ) ;
ans = strlen( S   1 ) ;
for (int i = 1 ; i <= ans ; i    )