Longest Substring with At Most Two Distinct Characters

Given a string s, determine the length of the longest substring that contains at most two distinct characters.

For example, consider the string eceba. The longest substring with at most two distinct characters is ece, which has length 3.

This problem can be solved efficiently using the sliding window technique. The main idea is to maintain a window that satisfies the condition and expand or contract the window whenever the number of distinct characters exceeds two.

It is guaranteed that the input strings contain only lowercase English letters.

Mathematically, if we let \(f(s)\) denote the length of the longest valid substring of s, then for each test case, you need to compute:

\[ f(s)=\max\{ |s[i\ldots j]| : s[i\ldots j] \text{ contains at most two distinct characters} \} \]

inputFormat

The first line of input contains a single integer T — the number of test cases.

Each of the following T lines contains a string s. Note that the string may be empty.

outputFormat

For each test case, output a single line containing the length of the longest substring of s that contains at most two distinct characters.

## sample

7
eceba
ccaabbb

a
aa
abababab
abcabcabc

3
5
0
1
2
8
2

</p>