Given a string s, partition s such that every substring of the partition is a palindrome. Find the minimum cuts needed for palindromic partition of s.

Example:

s: “aabc”
Min cuts: 2
Palindromic partition: [“aa”, “b”, “c”]

Testing

Input Format

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

For each test case, the input has one line with the string ‘s’.

Output format

For each test case, the output has one line containing an integer denoting the minimum number of cuts.

Sample Input

4
aabc
aca
hot
coffee

Expected Output

2
0
2
3

Constraints

1 <= T <= 10
1 <= length of s <= 200
Each character of s is a lowercase english alphabet.