You are given a string S consisting of lowercase Latin letters. You have to select a substring say S1 and prefix say S2 from S of equal length.
Your task is to concatenate them such that one of them is appended in reverse order and form a string P that is either:
If string P is a palindrome, then it is said to be a special palindrome.
Find the number of strings S1 such that there exists a prefix S2 using which a special palindrome string can be formed.
Input format
Output format
For each test case, print the number of distinct special palindrome strings possible in a new line.
Constraints
1≤T≤101≤N≤103
All prefix strings are Special Palindrome strings, i.e. given strings are Special Palindrome :-