Run Length Encoding(RLE) is a simple form of compression. RLE consists of the process for searching for a repeated runs of a single character in a string to be compressed, and replacing them by a single instance of the character and a run count. For example, a string ‘abcccddddddefgggggggggghijk’ is encoded into a string ‘ab3c6def10ghijk’ by RLE. A new compression method similar to RLE is devised and the rule of the method is as follows: if a substring S is repeated k times, replace k copies of S by k(S). For example, ‘letsgogogo’ is compressed into ‘lets3(go)’. The length of ‘letsgogogo’ is 10, and the length of ‘lets3(go)’ is 9. In general, the length of k(S) is (number of digits in k) + (length of S) + 2 (for ‘(’ and ‘)’). For example, the length of ‘123(abc)’ is 8. It is also possible to nest compression, so the substring S may itself be a compressed string. For example, ‘nowletsgogogoletsgogogo’ could be compressed as a ‘now2(lets3(go))’, and ‘nowletsgogogoletsgogogoandrunrunrun’ could be compressed as ‘now2(lets3(go))and3(run)’. Write a program that, for a given string, gives a shortest compressed string using the compression rules as described above. Input Your program is to read from standard input. The input consists of T test cases. The number of test cases T is given in the first line of the input. Each test case consists of a single line containing one string of no more than 200 characters drawn from a lower case alphabet. The length of shortest input string is 1. Output Your program is to write to standard output. Print exactly one line for each test case. For each test case, print the length of the shortest compressed string. Sample Input 4 ababcd letsgogogo nowletsgogogoletsgogogo nowletsgogogoletsgogogoandrunrunrun Sample Output 6 9 15 24