Splits the string

<div style="color:#464646;font-family:Tahoma, Arial, sans-serif, simsun;font-size:14px;background-color:#FFFFFF;"> Hrdv is interested in a string,especially the palindrome string.So he wants some palindrome string. </div> <div style="color:#464646;font-family:Tahoma, Arial, sans-serif, simsun;font-size:14px;background-color:#FFFFFF;"> <br /> </div> <div style="color:#464646;font-family:Tahoma, Arial, sans-serif, simsun;font-size:14px;background-color:#FFFFFF;"> A sequence of characters is a palindrome if it is the same written forwards and backwards. For example, 'abeba' is a palindrome, but 'abcd' is not. </div> <div style="color:#464646;font-family:Tahoma, Arial, sans-serif, simsun;font-size:14px;background-color:#FFFFFF;"> <br /> </div> <div style="color:#464646;font-family:Tahoma, Arial, sans-serif, simsun;font-size:14px;background-color:#FFFFFF;"> A partition of a sequence of characters is a list of one or more disjoint non-empty groups of consecutive characters whose concatenation yields the initial sequence. For example, ('race', 'car') is a partition of 'racecar' into two groups. </div> <div style="color:#464646;font-family:Tahoma, Arial, sans-serif, simsun;font-size:14px;background-color:#FFFFFF;"> <br /> </div> <div style="color:#464646;font-family:Tahoma, Arial, sans-serif, simsun;font-size:14px;background-color:#FFFFFF;"> Given a sequence of characters, we can always create a partition of these characters such that each group in the partition is a palindrome! Given this observation it is natural to ask: what is the minimum number of groups needed for a given string such that every group is a palindrome? </div> <div style="color:#464646;font-family:Tahoma, Arial, sans-serif, simsun;font-size:14px;background-color:#FFFFFF;"> <br /> </div> <div style="color:#464646;font-family:Tahoma, Arial, sans-serif, simsun;font-size:14px;background-color:#FFFFFF;"> For example: </div> <div style="color:#464646;font-family:Tahoma, Arial, sans-serif, simsun;font-size:14px;background-color:#FFFFFF;"> <br /> </div> <div style="color:#464646;font-family:Tahoma, Arial, sans-serif, simsun;font-size:14px;background-color:#FFFFFF;"> 'racecar' is already a palindrome, therefore it can be partitioned into one group. </div> <div style="color:#464646;font-family:Tahoma, Arial, sans-serif, simsun;font-size:14px;background-color:#FFFFFF;"> 'fastcar' does not contain any non-trivial palindromes, so it must be partitioned as ('f', 'a', 's', 't', 'c', 'a', 'r'). </div> <div style="color:#464646;font-family:Tahoma, Arial, sans-serif, simsun;font-size:14px;background-color:#FFFFFF;"> 'aaadbccb' can be partitioned as ('aaa', 'd', 'bccb'). </div> <div style="color:#464646;font-family:Tahoma, Arial, sans-serif, simsun;font-size:14px;background-color:#FFFFFF;"> Input begins with the number n of test cases. Each test case consists of a single line of between 1 and 1000 lowercase letters, with no whitespace within. </div> <div> <br /> </div>

<span style="color:#464646;font-family:Tahoma, Arial, sans-serif, simsun;font-size:14px;line-height:21px;background-color:#FFFFFF;">Each test case consists of a single line of between 1 and 1000 lowercase letters, with no whitespace within.</span>

<span style="color:#464646;font-family:Tahoma, Arial, sans-serif, simsun;font-size:14px;line-height:21px;background-color:#FFFFFF;">For each test case, output a line containing the minimum number of groups required to partition the input into groups of palindromes.</span>