minimum cuts required in a string for partitioning

Given a string, a partitioning of the string is a palindrome partitioning if every substring of the partition is a palindrome. For example, “aba|b|bbabb|a|b|aba” is a palindrome partitioning of “ababbbabbababa”. Determine the fewest cuts needed for palindrome partitioning of a given string. For example, minimum 3 cuts are needed for “ababbbabbababa”. The three cuts are “a|babbbab|b|ababa”. If a string is palindrome, then minimum 0 cuts are needed. If a string of length n containing all different characters, then minimum n-1 cuts are needed. Write a program to have Minimum cuts needed for Palindrome Partitioning of a string. Input The input file is named as in4.dat. The first line will contain N (1<=N<=100) indicating number of test cases. The subsequent lines will consist of a string (1<=P<=100). Output The output file named as out4.dat. For each test case in the input, print the Minimum cuts needed for Palindrome Partitioning of a string. Sample Input 1 ababbbabbababa Sample Output 3