A. Игра со сдвигом строк
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Назовём блоком в строке непрерывную подстроку одинаковых символов, которую нельзя расширить ни влево, ни вправо. Например, в строке aabcccdaa есть пять блоков:

  • aa (с $$$1$$$-го по $$$2$$$-й символ)
  • b ($$$3$$$-й символ)
  • ccc (с $$$4$$$-го по $$$6$$$-й символ)
  • d ($$$7$$$-й символ)
  • aa (с $$$8$$$-го по $$$9$$$-й символ).

Вы играете в игру, где вам дана строка $$$s$$$ длиной $$$n$$$. Вы можете циклически сдвигать$$$^{\text{∗}}$$$ строку как вам угодно. Ваш счёт затем рассчитывается как количество блоков в финальной строке. Найдите максимальный возможный счёт.

$$$^{\text{∗}}$$$Формально, выберите индекс $$$1 \leq i \leq n$$$ и замените строку $$$s_1s_2\ldots s_n$$$ на строку $$$s_{i+1}s_{i+2}\ldots s_ns_1s_2\ldots s_{i}$$$. Например, строку abcde можно сдвинуть в строку deabc, выбрав $$$i=3$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 500$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 100$$$).

Вторая строка каждого набора входных данных содержит строку $$$s$$$ длиной $$$n$$$.

Строка $$$s$$$ состоит только из строчных латинских букв.

Выходные данные

Для каждого набора входных данных выведите одно целое число — максимальный счёт, который вы можете получить.

Пример
Входные данные
4
4
abcd
4
abbc
4
abba
6
abbccc
Выходные данные
4
4
3
4
Примечание

В первом наборе входных данных счёт оригинальной строки abcd равен $$$4$$$. Можно показать, что счёт больше $$$4$$$ получить невозможно.

Во втором наборе входных данных циклический сдвиг строки на $$$2$$$ позиции даст нам строку bcab. Счёт этой строки равен $$$4$$$. Можно показать, что счёт больше $$$4$$$ получить невозможно.