Palindrome Partitioning ll

Given a string ‘str’. Find the minimum number of partitions to make in the string such that every partition of the string is a palindrome.

Given a string, make cuts in that string to make partitions containing substrings with size at least 1, and also each partition is a palindrome. For example, consider “AACCB” we can make a valid partition like A | A | CC | B. Among all such valid partitions, return the minimum number of cuts to be made such that the resulting substrings in the partitions are palindromes.

The minimum number of cuts for the above example will be AA | CC | B. i.e 2 cuts

Note :

1) We can partition the string after the first index and before the last index.

2) Each substring after partition must be a palindrome.

3) For a string of length ‘n’, if the string is a palindrome, then a minimum 0 cuts are needed.  

4) If the string contains all different characters, then ‘n-1’ cuts are needed.

5) The string consists of upper case English alphabets only with no spaces.

Input format :

The first line of input contains an integer ‘T’ denoting the number of test cases.
The next ‘T’ lines represent the ‘T’ test cases.

Each test case on a separate line contains a string ‘str’ denoting the string to be partitioned.

Output Format :

 For each test case, return the minimum number of cuts to be done so that each partitioned substring is a palindrome.

Constraints :

1 <= T <= 50
1 <= length(string) <= 100


Where ‘T’ is the total number of test cases, ‘length(string)’ denotes the length of the string.

Time limit: 1 second