Влад решил записать мелодию на своей гитаре. Представим мелодию как последовательность нот, которым соответствуют символы 'a', 'b', 'c', 'd', 'e', 'f' и 'g'.
Однако, он не очень опытен в игре на гитаре и может записать ровно две ноты за раз. Влад хочет получить мелодию \(s\) и для этого он может сводить записанные мелодии вместе. При этом, последний звук в первой мелодии должен совпадать с первым звуком второй мелодии.
Например, если Влад записал мелодии «ab» и «ba», он может свести их вместе и получить мелодию «aba», а потом свести результат с «ab» и получить «abab».
Помогите Владу определить, какое минимальное количество мелодий из двух нот ему нужно записать, чтобы получить мелодию \(s\).
Выходные данные
Выведите \(t\) целых чисел, каждое из которых является ответом на соответствующий набор входных данных. В качестве ответа выведите минимальное количество мелодий из двух нот, которое нужно записать Владу.
Примечание
В первом примере нужно записать мелодии «ab» и «ba», как и было описано в условии.
Во втором примере нужно записать мелодии «ab», «ba», «aс» и «сa».
В третьем примере единственная необходимая мелодия это «aa».
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
4
abab
7
abacaba
6
aaaaaa
7
abcdefg
5
babdd
|
2
4
1
6
4
|