Cho một xâu ký tự ~S~. Ta thực hiện chia xâu ~S~ thành ~k~ xâu con liên tiếp không rỗng: ~s_1, s_2, \dots, s_k~ sao cho khi ghép chúng lại theo đúng thứ tự, ta thu được xâu ban đầu (tức là ~S = s_1 + s_2 + \dots + s_k~).

Cách chia này được gọi là đối xứng nếu dãy các xâu con tạo thành một cấu trúc đối xứng (palindrome). Nói cách khác, xâu con thứ ~i~ từ đầu phải giống hệt xâu con thứ ~i~ từ cuối, hay:

$$s_i = s_{k - i + 1} \quad \forall 1 \le i \le k$$

• Ví dụ, với xâu "decode", ta có hai cách chia đối xứng sau:
• Chia thành ~3~ phần: (de)(co)(de) (vì xâu con thứ nhất "de" bằng xâu con thứ ba "de").
• Chia thành ~1~ phần: (decode) (mọi xâu luôn có ít nhất cách chia mặc định này với ~k = 1~).

Yêu cầu: Cho một xâu ~S~, hãy tìm cách chia đối xứng sao cho số lượng xâu con ~k~ thu được là lớn nhất.

Input

Dòng đầu tiên chứa số nguyên ~T \le 5~ — số lượng bộ dữ liệu thử nghiệm (test case).

~T~ dòng tiếp theo, mỗi dòng chứa một xâu ~S~ chỉ gồm các chữ cái tiếng Anh viết thường và không chứa khoảng trắng.

Output

Với mỗi bộ dữ liệu, in ra một số nguyên duy nhất trên một dòng — số lượng xâu con lớn nhất ~k~ của cách chia đối xứng tìm được.

Scoring

Trong các subtask, ~T \le 5~ và gọi ~L~ là độ dài của xâu ~S~ ứng mỗi test case.

Sample Input 1

5
decode
deleted
sicthaui
amanaplanacanalpanama
jokerqueenqueenjoker

Sample Output 1

3
5
1
21
4

Giải thích

• Ví dụ đầu tiên đã được giải thích trong đề bài.
• Ở ví dụ thứ hai, xâu "deleted" có cách chia đối xứng dài nhất gồm ~5~ phần: (d)(e)(let)(e)(d).