Feluda likes palindromes very much. He is so fond of palindromes that if you give him any string, he will try to break it into continuous palindromes.

As Feluda is a smart boy, he will do try to break the string into minimum number of such continuous palindromes. You have to help Prabhu. Find out the answer for the problem if he is given a string s.

Input

T : number of test cases (T <= 100)
next T lines contain a string s (length of s <= 2000)

Output

For every test case print one line having answer as given in the problem statement.

Example

Input:
4
abacdc
ababa
ababbacababbad
abcd
 
Output:
2
1
5
4