Stable String

You are given a string consisting only of the opening brace { and the closing brace }. Find the minimum number of operations needed to turn it into a stable string.

A stable string is defined as follows.

1. The empty string is stable.
2. If a string $S$ is stable, then ${S}$ is also stable.
3. If strings $S$ and $T$ are stable, then their concatenation $ST$ is also stable.

For example, {}, {}{}, and {{}{}} are stable, while }{, {{}{, and {}{ are not.

Two operations may be applied to the string:

• Change an opening brace { into a closing brace }.
• Change a closing brace } into an opening brace {.

The input consists of several data sets. Each data set is a single line containing a string made up only of the opening brace { and the closing brace }. Each string is at most $2000$ characters long, and its length is always even.

The last line of the input contains one or more hyphens -; this line is not processed.

Print one line for each data set. Each line contains the number of the data set (starting from $1$, numbered in the order the data sets appear) and the minimum number of operations needed to make its string stable, in the format number. count.