팰린드롬 분할

문자열 $s$의 분할은 비어 있지 않은 부분 문자열 $a_1, a_2, \dots, a_d$를 겹치지 않게 골라 $s = a_1 + a_2 + \dots + a_d$가 되도록 만든 것이다. 각 부분 문자열을 조각이라고 부르고, 조각의 개수 $d$를 그 분할의 길이라고 한다.

분할은 조각마다 괄호를 씌워서 나타낸다. 예를 들어 문자열 decode는 (d)(ec)(ode), (d)(e)(c)(od)(e), (decod)(e), (decode), (de)(code)처럼 여러 가지로 분할된다.

조각 하나를 더 쪼갤 수 없는 단위로 볼 때 조각의 나열이 앞에서 읽으나 뒤에서 읽으나 같으면, 그 분할을 팰린드롬 분할이라고 한다. decode의 팰린드롬 분할은 (de)(co)(de)와 (decode) 두 가지뿐이다. 뒤쪽 예에서 보듯 어떤 단어에도 길이가 1인 팰린드롬 분할이 항상 존재한다.

단어 $s$가 주어지면 팰린드롬 분할의 길이가 최대 얼마인지 구하여라.

첫째 줄에 테스트 케이스의 개수 $t$가 주어진다. 이어지는 $t$개의 줄에 테스트 케이스가 한 줄에 하나씩 주어진다. 각 줄에는 영어 소문자로만 이루어진 단어 $s$가 하나 있고, 입력에 공백은 없다.

각 테스트 케이스마다 단어 $s$의 팰린드롬 분할 중 가장 긴 것의 길이를 한 줄에 하나씩 출력한다.

단어 $s$의 길이를 $n$이라고 하자.

• $1 \le t \le 10$
• $1 \le n \le 10^6$