주문 시전

주문을 시전하는 것은 현실을 다루는 기술 중에서도 가장 이해하기 어려운 기술이다. 사람들은 진짜 주문(예: 전투에서 쓰이고 마법 대학에서 가르치는 abrahellehhelleh)과 단순한 고함(예: 배우지 못한 마녀가 고양이에게 지르는 rachelhellabracadabra)을 구분하기 어려워한다.

Unheard University의 연구는 마침내 단어(진짜 주문이든 고함이든)의 힘(power)을 측정하는 방법을 밝혀냈다. 그 힘은 단어를 거꾸로 발음하는 능력과 관련이 있다. 형식적으로, 단어의 힘은 $ww^Rww^R$ 꼴을 이루는 가장 긴 부분 문자열의 길이이다. 여기서 $w$는 임의의 문자열이고 $w^R$은 $w$를 뒤집은 것이다. 그러한 부분 문자열이 없으면 힘은 $0$이다.

예를 들어 abrahellehhelleh의 힘은 $12$인데, hellehhelleh($w=$ hel)를 포함하기 때문이다. rachelhellabracadabra의 힘은 $0$이다. 단어의 힘은 항상 $4$의 배수임에 유의하라.

여러 개의 테스트 케이스가 주어진다. 첫 줄에는 테스트 케이스의 수를 나타내는 정수 $Z$ ($1 \le Z \le 40$)가 주어진다. 이어지는 $Z$개의 줄에는 각각 하나의 단어가 주어진다.

각 단어의 길이는 최대 $3 \cdot 10^5$이며, 영어 알파벳 대문자와 소문자로만 이루어진다. 문자는 대소문자를 구분한다.

각 테스트 케이스마다 해당 단어의 힘을 정수 하나로 출력한다.