Description
Although you have helped Mr.Moriya to partition the string, he doesn't think it is enough.
He wants everything to become symmetry faster and faster!
You should help Mr.Moriya partition the string to symmetry by minimal cut.
Otherwise, he will use the boom to destroy the world.
Given a string S, partition S such that every substring of the partition is a palindrome (symmetry) and outputs the minimal cuts needed for a palindrome (symmetry) partitioning of S.
Example1: S = "aab" can be partitioned to ["aa", "b"], ["a", "a", "b"] these 2 conditions, ["aa", "b"] condition can be produced with a minimal cut: 1 in all conditions(["a", "a", "b"] needs 2 cuts).
Example2: S = "c" can be partitioned to ["c"] 1 condition, so ["c"] condition can be produced with a minimal cut: 0 in all conditions.
Input
The first line of the input is an integer T, denoting the number of testcases. 1<= T <= 10
Next T lines indicate T strings S to partition
1 <= length of S <= 1000
Note that S only contains lowercase English alphabets.
Output
Output how many methods to partition S.
Output the minimal cut to partition S.
Remember to output '\n' at the end of each line.