22162_GenerateString

ZZZ wants to generate a sequence of characters starting from an empty string using the following method.

First, S₀ = "" is an empty string.

For a generated string S_k, he can chooses any position to split S_k into two continuous string S_k1 and S_k2. Notice that either S_k1 or S_k2 may be empty. Then he can add a string S_k0, which consists of only a single kind of character, to concatenate them. So S_k+1 = S_k1 + S_k0 + S_k2.

Your task is to help ZZZ to generate a given string using minimum steps.

Take the following example.

S = "aabbaab"

S₀ = ""

S₁ = "aaaa"

S₂ = "aabbaa"

S₃ = "aabbaab"

The first line of input there is one integer T ( T ≤ 100 ), giving the number of test cases in the input. Each test case contains a line with string S. The length of S is no more than 200. S is made up of only lowercase letters.

For each test case, output the number of minimum steps.

2
a
aabbaab

1
3