종이 접기

헥토르는 수업이 지루해서 직접 놀이를 하나 만들었다. 종이를 길게 잘라 그 위에 0과 1로 이루어진 문자열을 적었다 (예: 10000101011). 이제 인접한 두 기호 사이를 접어서, 접혀 올라온 부분이 그 아래로 겹치는 부분과 맞아떨어지게 하려고 한다. 규칙은 겹치는 자리의 기호가 서로 같아야 한다는 것이다. 헥토르는 항상 왼쪽 부분을 오른쪽으로 접는다. 즉 접는 선을 기준으로 왼쪽 조각이 뒤집혀 오른쪽 조각 위에 포개진다.

예를 들어 10000101011을 세 번째와 네 번째 기호 사이에서 접으면 00101011이 되고, 끝에서 두 번째와 마지막 기호 사이에서 접으면 1010100001이 된다. 접은 뒤 종이의 길이는 두 조각 중 더 긴 쪽의 길이가 된다.

헥토르는 이렇게 (필요하면 여러 번) 접어서 종이를 가능한 한 짧게 만들고 싶다. 예를 들어 10011001은 먼저 네 번째와 다섯 번째 기호 사이에서 접어 1001을 얻고, 다시 두 번째와 세 번째 기호 사이에서 접으면 01이 되어 길이 $2$까지 줄일 수 있다.

여러 번 접어서 얻을 수 있는 종이의 가장 짧은 길이를 구하여라.

첫 줄에 테스트 케이스의 수 $t$가 주어진다 ($1 \le t \le 20$). 이어서 $t$개의 테스트 케이스가 주어진다.

각 테스트 케이스는 한 줄로 이루어지며, 헥토르의 종이를 나타내는 0과 1의 문자열이 아무 구분 기호 없이 주어진다. 이 문자열의 길이는 $1$ 이상 $100$ 이하이다.

각 테스트 케이스마다 한 줄에 정수 하나를 출력한다. 그 값은 (필요하면 여러 번) 접어서 얻을 수 있는 가장 짧은 종이의 길이이다.