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
be1035016: 2018-06-30 08:26:53

nice problem:) AC in one go

kira28: 2016-12-29 16:43:08

Finally solved it!!!
O(N^2) :) memoization reqd for palindromes too

Last edit: 2016-12-29 17:00:32
birdie: 2015-08-08 13:52:56

Top down dp- tle! bottom up - ac


Last edit: 2015-08-09 10:16:24
priya choudhary: 2015-01-18 12:49:21

Every test case is running on my code..:( still getting WA
plzz..check my submission id is 13458258

rishabh aggarwal: 2014-12-23 19:38:57

nice problem...

Aditya Joshi: 2014-10-09 10:59:08

@satyajit ganguly: For ababbacababbad, you get aba + b + bacab + abba + d = 5.

For ababbd, aba + bb + d = 3.

Rishi: 2014-09-21 21:16:29

explain the ouput for: ababbd

Rishi: 2014-09-21 20:08:56

please explain the output for 3rd case...how did you get 5? what are the palindromes?

Archit Jain: 2014-07-31 20:13:06

o(n^3) TLE
o(n^2) AC

Noob: 2014-04-24 11:42:45

Nice problem :)


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