La subcadena ordenada de Nasser

Entrada

Cada test contiene múltiples casos de prueba. La primera línea contiene un único entero $t$ (1 \le t \le 10^4) — el número de casos de prueba. A continuación sigue la descripción de los casos de prueba.

La primera línea de cada caso de prueba contiene un entero $n$ (1 \le n \le 2 \cdot 10^5) — la longitud de la cadena.

La segunda línea de cada caso de prueba contiene una cadena $s$ de longitud $n$, formada por letras minúsculas del alfabeto inglés (de 'a' a 'z').

Se garantiza que la suma de $n$ sobre todos los casos de prueba no excede 2 \cdot 10^5.

Salida

Para cada caso de prueba, imprime un único entero — la longitud de la subcadena ordenada más larga que se puede obtener después de realizar a lo sumo un cambio de carácter.

Ejemplos

Nota

En el tercer caso de prueba, n=4, s=\texttt{``abca''}:

• La cadena no está completamente ordenada, ya que s[3]=\texttt{'c'} > s[4]=\texttt{'a'}.

• Podemos cambiar s[4]=\texttt{'a'} por $\text{’c’}$: $s$ se convierte en $\text{‘‘abcc’’}$, que está completamente ordenada. Longitud $=4$.

• También podemos cambiar s[4]=\texttt{'a'} por $\text{’z’}$: $s$ se convierte en $\text{‘‘abcz’’}$, que está completamente ordenada. Longitud $=4$.

• Ningún cambio único puede dar una subcadena ordenada de longitud mayor que $4$.

• Respuesta: $4$.

Puntuación

1. Subtarea $1$ ($40$ puntos) : (1 \le \sum n \le 1000)

2. Subtarea $2$ ($60$ puntos) : La cadena $s$ consta de a lo sumo $2$ caracteres distintos.

3. Subtarea $3$ ($100$ puntos) : Sin restricciones adicionales.