스택으로 전광판 메시지 만들기

문제

고속도로 위에 걸린 전광판의 메시지를 관리하는 일을 맡았다. 이 전광판에는 메모리가 없어서 메시지를 바꿀 때마다 사람이 직접 입력해야 한다.

입력 장치는 문자를 담는 스택 하나뿐이고, 쓸 수 있는 연산은 세 가지다.

push c: 문자 c를 스택의 맨 위에 넣는다.
pop: 스택의 맨 위에 있는 문자를 뺀다.
print: 스택의 맨 위에 있는 문자를 전광판에 이어서 출력한다.

주어진 메시지를 출력하되 연산 횟수를 최소로 하려고 한다. 다음 메시지를 바로 입력할 수 있도록, 작업이 끝난 뒤 스택은 비어 있어야 한다.

메시지 abba는 연산 8번으로 출력할 수 있다. 아래 표에서 스택은 오른쪽 끝이 맨 위다.

	연산	스택 내용	출력된 메시지
1	`push a`	`a`
2	`print`	`a`	`a`
3	`push b`	`ab`	`a`
4	`print`	`ab`	`ab`
5	`print`	`ab`	`abb`
6	`pop`	`a`	`abb`
7	`print`	`a`	`abba`
8	`pop`		`abba`

abba를 정확히 출력하고 스택을 비우는 연산 순서 중에 8번보다 짧은 것은 없다.

메시지가 주어질 때 필요한 최소 연산 횟수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 메시지의 개수 $T$ ( $1 \le T \le 30$ )가 주어진다. 다음 $T$ 개 줄에 메시지가 한 줄에 하나씩 주어진다. 각 메시지는 출력 가능한 문자로 이루어지고, 길이는 1자 이상 200자 이하이며, 첫 글자와 마지막 글자는 공백이 아니다. 메시지 중간에는 공백이 들어갈 수 있다.

출력

각 메시지마다 그 메시지를 전광판에 출력하고 스택을 비우는 데 필요한 최소 연산 횟수를 한 줄에 하나씩 출력한다.