Nasser'in Sıralı Alt Dizgisi

Giriş

Her test birden fazla test durumu içerir. İlk satırda tek bir tam sayı $t$ (1 \le t \le 10^4) — test durumlarının sayısı verilir. Ardından test durumlarının açıklaması gelir.

Her test durumunun ilk satırında bir tam sayı $n$ (1 \le n \le 2 \cdot 10^5) — dizginin uzunluğu verilir.

Her test durumunun ikinci satırında küçük İngiliz harflerinden ('a' ile 'z' arası) oluşan $n$ uzunluğunda bir $s$ dizgisi verilir.

Tüm test durumları üzerinden $n$ değerleri toplamının 2 \cdot 10^5 değerini aşmadığı garanti edilir.

Çıktı

Her test durumu için tek bir tam sayı — en fazla bir karakter değişikliği yapıldıktan sonra elde edilebilecek en uzun sıralı alt dizginin uzunluğunu yazdırın.

Örnekler

Not

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

• s[3]=\texttt{'c'} > s[4]=\texttt{'a'} olduğundan dizgi tamamen sıralı değildir.

• s[4]=\texttt{'a'} karakterini $\text{’c’}$ ile değiştirebiliriz: $s$ $\text{‘‘abcc’’}$ olur ve tamamen sıralı hale gelir. Uzunluk $=4$.

• Ayrıca s[4]=\texttt{'a'} karakterini $\text{’z’}$ ile de değiştirebiliriz: $s$ $\text{‘‘abcz’’}$ olur ve tamamen sıralı hale gelir. Uzunluk $=4$.

• Tek bir değişiklikle uzunluğu $4$'ten büyük sıralı bir alt dizgi elde edilemez.

• Cevap: $4$.

Puanlama

1. Alt görev $1$ ($40$ puan) : (1 \le \sum n \le 1000)

2. Alt görev $2$ ($60$ puan) : $s$ dizgisi en fazla $2$ farklı karakterden oluşur.

3. Alt görev $3$ ($100$ puan) : Ek kısıtlama yoktur.