Think about the Zuma Game. You have a row of at most $200$ black(0) or white(1) balls on the table at the start. Each three consecutive balls never share the same colour. You also have infinite amount of black and white balls in your hand. On each turn, you can choose a ball in your hand and insert it into the row, including the leftmost place and the rightmost place. Then, if there is a group of three of more balls in the same colour touching, remove these balls. Keep doing this until no more balls can be removed.

Find the minimal balls you have to insert to remove all the balls on the table.

Find the minimal balls you have to insert to remove all the balls on the table.

The first line of input contains an integer $T~(1\le T\le 100)$ which is the total number of test cases.

Each test case contains a line with a non-empty string of $0$ and $1$ describing the row of balls at the start.

Each test case contains a line with a non-empty string of $0$ and $1$ describing the row of balls at the start.

提交代码