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

Влад решил записать мелодию на своей гитаре. Представим мелодию как последовательность нот, которым соответствуют символы 'a', 'b', 'c', 'd', 'e', 'f' и 'g'.

Однако, он не очень опытен в игре на гитаре и может записать ровно две ноты за раз. Влад хочет получить мелодию $$$s$$$ и для этого он может сводить записанные мелодии вместе. При этом, последний звук в первой мелодии должен совпадать с первым звуком второй мелодии.

Например, если Влад записал мелодии «ab» и «ba», он может свести их вместе и получить мелодию «aba», а потом свести результат с «ab» и получить «abab».

Помогите Владу определить, какое минимальное количество мелодий из двух нот ему нужно записать, чтобы получить мелодию $$$s$$$.

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

В первой строке входных данных содержится целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных в тесте.

Далее следуют описания наборов.

Первая строка набора содержит целое число $$$n$$$ ($$$2 \le n \le 50$$$) — длина мелодии $$$s$$$.

Вторая строка набора содержит строку $$$s$$$ из $$$n$$$ символов, каждый из которых 'a', 'b', 'c', 'd', 'e', 'f' или 'g'.

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

Выведите $$$t$$$ целых чисел, каждое из которых является ответом на соответствующий набор входных данных. В качестве ответа выведите минимальное количество мелодий из двух нот, которое нужно записать Владу.

Пример
Входные данные
5
4
abab
7
abacaba
6
aaaaaa
7
abcdefg
5
babdd
Выходные данные
2
4
1
6
4
Примечание

В первом примере нужно записать мелодии «ab» и «ba», как и было описано в условии.

Во втором примере нужно записать мелодии «ab», «ba», «aс» и «сa».

В третьем примере единственная необходимая мелодия это «aa».