IITKWPCE - Let us play with strings


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

hide comments
anurag garg: 2014-01-11 20:07:09

optimized brute force will work...

 : 2013-11-30 10:17:08

Finally,...AC thanks

 : 2013-11-27 15:15:39

TLE :(

[Lakshman]: 2013-09-13 06:26:27

@Shaka Shadows Thanks AC with O(|s| ^ 2)

Shaka Shadows: 2013-09-12 13:19:55

@Lakshman O(|s| ^ 2) is enough.

[Lakshman]: 2013-09-12 11:21:30

@PS what is the expected complexity for this.
getting TLE.


Added by:praveen123
Date:2013-08-05
Time limit:1s-3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:IITK ACA CSE online judge