Nasser's Sorted Substring

Input

Each test contains multiple test cases. The first line contains a single integer $t$ (1 \le t \le 10^4) — the number of test cases. The description of the test cases follows.

The first line of each test case contains an integer $n$ (1 \le n \le 2 \cdot 10^5) — the length of the string.

The second line of each test case contains a string $s$ of length $n$, consisting of lowercase English letters ('a' to 'z').

It is guaranteed that the sum of $n$ over all test cases does not exceed 2 \cdot 10^5.

Output

For each test case, print a single integer — the length of the longest sorted substring that can be achieved after performing at most one character change.

Examples

Note

In the third test case, n=4, s=\texttt{``abca''}:

• The string is not fully sorted since s[3]=\texttt{'c'} > s[4]=\texttt{'a'}.

• We can change s[4]=\texttt{'a'} to $\text{’c’}$: $s$ becomes $\text{‘‘abcc’’}$, which is fully sorted. Length $=4$.

• We can also change s[4]=\texttt{'a'} to $\text{’z’}$: $s$ becomes $\text{‘‘abcz’’}$, which is fully sorted. Length $=4$.

• No single change can give a sorted substring of length greater than $4$.

• Answer: $4$.

Scoring

1. Subtask $1$ ($40$ points) : (1 \le \sum n \le 1000)

2. Subtask $2$ ($60$ points) : The string $s$ consists of at most $2$ distinct characters.

3. Subtask $3$ ($100$ points) : No additional constraints.