You are given a string ~S~ of length ~N~ of lowercase letters. You are allowed to choose an index ~i~ ~(0 \le i < N)~ and replace ~S[i]~ with a different lowercase letter at most once. Determine the longest substring of identical characters in the string ~S~ after replacing a character at most once.

Constraints

~1 \le T \le 10^6~

~1 \le N \le 10^6~

The sum of ~N~ over all test cases does not exceed ~10^6~.

Input Specification

The first line contains a single integer ~T~, representing the number of test cases.

For each test case, there are two lines:

The first line contains a single integer ~N~.

The second line contains a string ~S~ of length ~N~.

Output Specification

For each test case, output a single integer: the length of the longest substring of identical characters in ~S~ after replacing a character at most once.

Sample Input

3
3
abc
4
aaab
4
baaa

Sample Output

2
4
4

Sample Explanation

For the first test case, changing any character to match one of its neighbors yields a substring of length ~2~ with identical characters.

In the second test case, changing the last character to a yields aaaa as a substring with identical characters.

In the third test case, changing the first character to a also yields aaaa as a substring.