sahil-and-his-love

Sahil loves palindromes.

He has a string with him. But, while he went out for some time, his brother changed his string in his

absence. When he comes back, he is very quick to observe what change has been done to his string.

He observes that the only change that has been done to his string, is that a suffix of the string has

been replaced by its reverse. He is fascinated by this change as now he is able to make a larger

palindrome from this string by removing some (or none) characters from the string. He starts

wondering what change of the given type, which his brother made, should he make on his string so

that he can make the longest possible palindrome by removing zero or more characters. He

wants to know the length of this longest possible palindrome. Since the T20 World Cup is going on

and he loves cricket even more than he loves palindromes, he doesn't want to miss the World Cup.

He turns to you for help. You need to now help him and tell him the answer for the string he has.

Note : You have to make exactly one change of the given type.

Input :

First line contains an integer T, the number of Test cases.

Each test case contains one string s, for which you need to tell the answer to the problem.

Constraints :

T ≤ 100

|s| ≤ 100

Output :

One number per line. The answer to his problem for the string s.

Problem setter : Sahil Prakash

SAMPLE INPUT
2
abcd
abab

SAMPLE OUTPUT
1
4

Explanation

for test 2 : if the suffix 'ab' is reversed. New string = 'abba'. In this case, the longest possible palindrome by removing zero or more characters is of length 4, hence the answer.

Source: hackerearth | Difficulty: EASY


Solutions: