Read problems statements in Mandarin Chinese , Russian and Vietnamese

Divyam is teaching his student Amit about palindromes. A palindrome is a word, phrase, number, or other sequence of characters which reads the same backward or forward. For example, the string “abcba” is a palindrome. After teaching about it, Divyam gave a puzzle for Amit to solve:

Given a string S. Find the number of positions in S where we can insert a character to convert it into a palindrome. Character can be inserted in the beginning or the end, so there will be (N+1) possible positions for the insertion in a string having original length N. For example, if S = “aaa”, then there are four positions where we can insert a character so that the converted string is a palindrome. Converted palindromes are “aaaa”, “aaaa”, “aaaa” and “aaaa”. Inserted character is shown in boldface.

Amit finds the puzzle too difficult. Can you help him in solving it?

------ Input ------

First line of input contains an integer T denoting the number of test cases.
First line of each test case will contain a string S containing lowercase letters only.

------ Output ------

Print T lines, each containing an integer: the solution for the corresponding test case.

------ Constraints ------

Subtask #1: 20 points

$1 ≤ T  ≤ 5, 1 ≤ length of string ≤ 1000$

Subtask #2: 80 points

$1 ≤ T  ≤ 5,  1 ≤ length of string ≤ 10^{5}$

----- Sample Input 1 ------
2

aaa

aca
----- Sample Output 1 ------
4

2
----- explanation 1 ------

First sample has been explained in the problem statement.

见题面

见题面