Skibidus is given a string $$$s$$$ that consists of lowercase Latin letters. If $$$s$$$ contains more than $$$1$$$ letter, he can:

Choose an index $$$i$$$ ($$$1 \leq i \leq |s| - 1$$$, $$$|s|$$$ denotes the current length of $$$s$$$) such that $$$s_i = s_{i+1}$$$. Replace $$$s_i$$$ with any lowercase Latin letter of his choice. Remove $$$s_{i+1}$$$ from the string.

Skibidus must determine the minimum possible length he can achieve through any number of operations.

Input

The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 100$$$) — the number of test cases.

The only line of each test case contains a string $$$s$$$ ($$$1 \leq |s| \leq 100$$$). It is guaranteed $$$s$$$ only contains lowercase Latin letters.

Output

For each test case, output an integer on the new line, the minimum achievable length of $$$s$$$.

Note

In the first test case, Skibidus can:

Perform an operation on $$$i = 2$$$. He replaces $$$s_2$$$ with b and removes $$$s_3$$$ from the string. Then, $$$s$$$ becomes bb.
Perform an operation on $$$i = 1$$$. He replaces $$$s_1$$$ with b and removes $$$s_2$$$ from the string. Then, $$$s$$$ becomes b.
Because $$$s$$$ only contains $$$1$$$ letter, Skibidus cannot perform any more operations.

Therefore, the answer is $$$1$$$ for the first test case.

In the second test case, he cannot perform an operation on any index. Therefore, the answer is still the length of the initial string, $$$8$$$.

Skibidus and Ohio

Examples