18256번 - Interleaved Periodic String 다국어

문제

An interleaved periodic string S can be written down using the following procedure:

1. Write down any two strings s₁ and s₂ of lengths p₁ and p₂ respectively. The strings must consist of only 0s and 1s, and can possibly be empty.
2. Concatenate some copies of the string s₁ to obtain string S₁.
3. Concatenate some copies of the string s₂ to obtain string S₂.
4. Interleave the strings S₁ and S₂ to obtain S.

To interleave two strings, merge their characters arbitrarily, maintaining the relative order in which they occur in both strings. For example, the strings “101” and “011” can be interleaved to get “011011” or “101011”, however they cannot be interleaved to form “110110”. Given S, find the minimum possible value of (p₁ + p₂).

입력

The input consists of multiple test cases. The first line contains the number of test cases T. Each of the next T lines contain a string S consisting of only ‘0’s and ‘1’s.

출력

Output T lines, one corresponding to each test case, containing the minimum value of (p₁ + p₂) for the corresponding test case.

제한

• 1 ≤ T ≤ 20
• 1 ≤ length of S ≤ 16

힌트