C :: Compression

Time Limit: 6 Seconds    Memory Limit: 32768 KB

Our university researchers are interested in a particular string coding method. Consider a string of lowercase English letters ('a'-'z'). According to this coding method one can select a prefix of the string and optionally replace its non-overlapping occurrences in the string each with 'P' and its reverse occurrences in the string each with 'R'. The prefix itself is not replaced and is followed by 'X' only if any replacements have taken place already. As an example consider the string 'abaaabaabaaba'. The string has different representations with the prefix selected, among which are 'abaaabaabaaba', 'abaXaPabaP', and 'abaaXPbR'. As you can see, the coded string can easily be decoded back to its original form. Our researchers want to know the effectiveness of this coding as a compression technique. 

Having the original string at hand you are asked to help us know the shortest possible coding that can be created using this method.

Input

The first line of the input contains an integer T≤100 denoting the number of test-cases. Each test-case is a string of length of at most 25,000 provided on a separate line.

Output

For each test-case, output the shortest possible length of the code in a line.

Sample Input

2
abaaabaabaaba
abcdabcda

Sample Output

8
7

Submit

Source: 12th Iran Nationwide Internet Contest IV