Відсортований підрядок Нассера

Вхідні дані

Кожен тест містить декілька тестових випадків. Перший рядок містить одне ціле число $t$ $(1 \leq t \leq 1 0^{4})$ (1 \le t \le 10^4) — кількість тестових випадків. Далі йде опис тестових випадків.

Перший рядок кожного тестового випадку містить ціле число $n$ $(1 \leq n \leq 2 \cdot 1 0^{5})$ (1 \le n \le 2 \cdot 10^5) — довжину рядка.

Другий рядок кожного тестового випадку містить рядок $s$ довжиною $n$ , що складається з малих літер латинського алфавіту (від 'a' до 'z').

Гарантується, що сума $n$ за всіма тестовими випадками не перевищує $2 \cdot 1 0^{5}$ 2 \cdot 10^5.

Вихідні дані

Для кожного тестового випадку виведіть одне ціле число — довжину найдовшого відсортованого підрядка, який можна отримати після виконання не більше однієї заміни символу.

Приклади

Приклад 1

Loading

Примітка

У третьому тестовому випадку $n = 4$ n=4, $s = ‘‘abca’’$ s=\texttt{``abca''}:

Рядок не є повністю відсортованим, оскільки $s [3] = ’c’ > s [4] = ’a’$ s[3]=\texttt{'c'} > s[4]=\texttt{'a'}.
Можна замінити $s [4] = ’a’$ s[4]=\texttt{'a'} на $’c’$ : $s$ перетворюється на $‘‘abcc’’$ , що є повністю відсортованим. Довжина $= 4$ .
Також можна замінити $s [4] = ’a’$ s[4]=\texttt{'a'} на $’z’$ : $s$ перетворюється на $‘‘abcz’’$ , що є повністю відсортованим. Довжина $= 4$ .
Жодна одна заміна не дає відсортованого підрядка довжиною більше ніж $4$ .
Відповідь: $4$ .

Оцінювання

Підзадача $1$ ( $40$ балів) : $(1 \leq \sum n \leq 1000)$ (1 \le \sum n \le 1000)
Підзадача $2$ ( $60$ балів) : Рядок $s$ складається не більш ніж з $2$ різних символів.
Підзадача $3$ ( $100$ балів) : Без додаткових обмежень.