Nasserin sıralanmış alt sətri

Giriş

Hər test bir neçə test nümunəsi ehtiva edir. Birinci sətirdə bir tam ədəd $t$ (1 \le t \le 10^4) — test nümunələrinin sayı verilir. Sonra test nümunələrinin təsviri gəlir.

Hər test nümunəsinin birinci sətrində bir tam ədəd $n$ (1 \le n \le 2 \cdot 10^5) — sətrin uzunluğu verilir.

Hər test nümunəsinin ikinci sətrində kiçik ingilis hərflərindən ('a'-dan 'z'-ə qədər) ibarət $n$ uzunluqlu $s$ sətri verilir.

Bütün test nümunələri üzrə $n$ cəminin 2 \cdot 10^5 qiymətini aşmadığı təmin edilir.

Çıxış

Hər test nümunəsi üçün bir tam ədəd — ən çoxu bir simvol dəyişikliyindən sonra əldə edilə bilən ən uzun sıralanmış alt sətrin uzunluğunu çap edin.

Nümunələr

Qeyd

Üçüncü test nümunəsində n=4, s=\texttt{``abca''}:

• Sətir tam sıralanmayıb, çünki s[3]=\texttt{'c'} > s[4]=\texttt{'a'}.

• s[4]=\texttt{'a'} simvolunu $\text{’c’}$ ilə əvəz edə bilərik: $s$ $\text{‘‘abcc’’}$ olur və tam sıralanmış alınır. Uzunluq $=4$.

• Həmçinin s[4]=\texttt{'a'} simvolunu $\text{’z’}$ ilə əvəz edə bilərik: $s$ $\text{‘‘abcz’’}$ olur və tam sıralanmış alınır. Uzunluq $=4$.

• Heç bir tək dəyişiklik uzunluğu $4$-dən böyük olan sıralanmış alt sətir verə bilməz.

• Cavab: $4$.

Bal hesablama

1. Alt məsələ $1$ ($40$ bal) : (1 \le \sum n \le 1000)

2. Alt məsələ $2$ ($60$ bal) : $s$ sətri ən çoxu $2$ fərqli simvoldan ibarətdir.

3. Alt məsələ $3$ ($100$ bal) : Əlavə məhdudiyyət yoxdur.