Problem D
Stack Construction
Strangely, the only way to post messages is using an on-board stack. You can push a character onto the top of the stack, you can pop the character that is on top of the stack, and you can print the character that is on top of the stack..
Out of boredom, or perhaps the universal human desire to do as little work as possible to get the job done, you wonder what the minimum number of push, pop, and print are required to print a message your boss has told you to display. Oh, you must also ensure the stack is clear at the end so that you are ready to input a new message next time your boss asks you to do this.
Example If we want to print the message abba and then clear the stack you could do the following. Note the contents of the stack are recorded below with the top of the stack on the right.
|
operation |
stack contents |
displayed message |
|
|
1 |
push a |
a |
|
|
2 |
|
a |
a |
|
3 |
push b |
ab |
a |
|
4 |
|
ab |
ab |
|
5 |
|
ab |
abb |
|
6 |
pop |
a |
abb |
|
7 |
|
a |
abba |
|
8 |
pop |
abba |
In fact, this is the fewest operations that can be performed to print exactly the message abba and leave the stack empty.
Input
The first line of input is a single integer $T \leq 30$ indicating the number of test cases. Each of the following $T$ lines contains a single string consisting of any printable characters. The first and last character of each line will not be a space. Each line has at least one and at most $200$ characters.
Output
For each of the $T$ strings in the input, you should output on a single line the minimum number of operations required to print the string on the display.
| Sample Input 1 | Sample Output 1 |
|---|---|
4 d abba rollover ahead ogopogo spotted! |
3 8 34 38 |
