L. Memable Ace
time limit per test
1 second
memory limit per test
256 megabytes
input
max-pair.in
output
standard output

Pillow decided to give Khaled Hamed an easy problem and was surprised when Khaled Hamed solved it. Apparently, Pillow didn't know that blue coders can solve problems.

So we hope you all prove Pillow wrong by solving the given problem.

Given a string $$$S$$$ where $$$S_i \neq S_{i+1}$$$ for all $$$0 \leq i \leq |S| - 1$$$.

return the maximum distance between a pair $$$i$$$ and $$$j$$$ such that $$$i \lt j$$$ and $$$S_i \neq S_j$$$ where the distance between a pair is $$$j - i$$$.

Input

The first line contains an integer $$$T$$$ number of test cases where $$$(1 \leq T \leq 10)$$$.

The only line in each test case is the string $$$S$$$ consisting only of lowercase Latin letters where $$$(2 \leq |S| \leq 10^5)$$$.

Output

For each test case print the maximum distance between a pair satisfying the above conditions.

Example
Input
2
abcda
ababab
Output
3
5