A palindromic string is a string that reads the same forward and backward. You are given a string S and you are asked to insert minimum number of characters needed to make S a palindrome. (string consist of only lowercase alphabets)
Input
The first line of the input contains an integer t, the number of test cases. t test cases follow.
Each test case consists of one line, the string S. S will contain no whitespace characters.
Output
For each test case output one line containing a single integer denoting the minimum number of characters that must be inserted into S to make it a palindrome.
CONSTRAINTS:- |S|<=5000;
Input
1
mj
Output
1
Problem author:- Mohit jain