Description
Mr.Moriya is a famous architect.
All the buildings he designs have one unique feature: they are symmetrical.
In fact, Mr.Moriya can't stand anything that is not symmetry, such as computers, clothes, photos, and anything he can see.
One day, when Mr.Moriya reads a book, he almost drives himself crazy because most strings in the books are not symmetry.
Can you help poor Mr.Moriya to partition the string into symmetry?
Given a string S, partition S such that every substring of the partition is a palindrome(symmetry), and output how many methods to partition S.
Example1: S = "aab" can be partitioned to ["aa", "b"], ["a", "a", "b"] these 2 conditions, so output is 2.
Example2: S = "c" can be partitioned to ["c"] 1 condition, so output is 1.
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 <= 40
Note that S only contains lowercase English alphabets.
Output
Output how many methods to partition S.
Remember to output '\n' at the end of each line.