You are given a string of length of lowercase letters. You are allowed to choose an index and replace with a different lowercase letter at most once. Determine the longest substring of identical characters in the string after replacing a character at most once.
The sum of over all test cases does not exceed .
The first line contains a single integer , representing the number of test cases.
For each test case, there are two lines:
The first line contains a single integer .
The second line contains a string of length .
For each test case, output a single integer: the length of the longest substring of identical characters in after replacing a character at most once.
For the first test case, changing any character to match one of its neighbors yields a substring of length with identical characters.
In the second test case, changing the last character to
aaaa as a substring with identical characters.
In the third test case, changing the first character to
a also yields
aaaa as a substring.