Shortest Removable Substring

Given a string \( S \), your task is to remove a contiguous substring from \( S \) such that the remaining string contains no two adjacent characters that are the same. You should determine the minimum length of the substring that must be removed to achieve this condition.

Clarification: Removal means selecting a continuous block of characters. The resulting string is formed by concatenating the parts before and after the removed substring. If \( S \) already satisfies the condition, you must remove the entire string. Formally, if the length of \( S \) is \( n \) and \( S \) has no two consecutive identical characters then the answer is \( n \). Otherwise, if \( S \) contains at least one pair of adjacent equal characters (and \( n > 1 \)), the answer is \( 2 \) based on the problem constraints. A special case is when \( n = 1 \), where the answer is \( 1 \).

For example:

• For \( S = \texttt{aabcc} \), the answer is \( 2 \) because there is at least one adjacent duplicate.
• For \( S = \texttt{aaa} \), the answer is \( 2 \).
• For \( S = \texttt{abcd} \), since there are no adjacent duplicates, the entire string must be removed, so the answer is \( 4 \) (the length of \( S \)).

inputFormat

The input is read from standard input (stdin) and has the following format:

T
S1
S2
...
ST

Where \( T \) (\( 1 \leq T \leq 1000 \)) is the number of test cases, and each \( S_i \) is a non-empty string.

outputFormat

For each test case, output a single integer on a new line representing the minimum length of a substring that can be removed so that the remaining string has no two adjacent characters that are identical.

## sample

1
aabcc

2

</p>