인터리브 주기 문자열

시간 제한1초메모리 제한512 MB

요약

이진 문자열 S가 주어질 때, 두 이진 문자열의 반복을 교차 병합해 S를 만들 수 있는 두 문자열 길이 합의 최솟값을 구한다.

난이도: 어려움10점 중 8점
유형: 완전 탐색, 동적 계획법, 문자열, 구현
정답자: 아직 제출이 없습니다

문제

인터리브 주기 문자열 $S$ 는 다음 과정으로 만들 수 있다.

길이가 각각 $p_1$ , $p_2$ 인 두 문자열 $s_1$ , $s_2$ 를 적는다. 두 문자열은 0과 1로만 이루어져야 하며, 비어 있을 수도 있다.
$s_1$ 을 여러 번 이어 붙여 문자열 $S_1$ 을 만든다.
$s_2$ 를 여러 번 이어 붙여 문자열 $S_2$ 를 만든다.
$S_1$ 과 $S_2$ 를 인터리브하여 $S$ 를 만든다.

두 문자열을 인터리브한다는 것은 두 문자열에서 문자가 나타나는 상대적 순서를 유지하면서 문자를 임의로 합치는 것이다. 예를 들어 “101”과 “011”은 인터리브하여 “011011”이나 “101011”을 만들 수 있지만, “110110”은 만들 수 없다. $S$ 가 주어졌을 때, $(p_1 + p_2)$ 의 최솟값을 구하라.

입력

입력은 여러 개의 테스트 케이스로 이루어진다. 첫째 줄에 테스트 케이스의 수 $T$ 가 주어진다. 다음 $T$ 개의 줄에 ‘0’과 ‘1’로만 이루어진 문자열 $S$ 가 각각 주어진다.

출력

$T$ 개의 줄에 각 테스트 케이스에 대한 $(p_1 + p_2)$ 의 최솟값을 한 줄에 하나씩 출력한다.

제한

$1 \le T \le 20$
$1 \le$ $S$ 의 길이 $\le 16$

예제1

예제 1
입력
```
1
0101
```
예상 출력
```
2
```