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

Вам дана строка $$$s$$$ длины $$$n$$$. Определим две операции, которые можно применить к строке:

  • удалить первый символ строки;
  • удалить второй символ строки.

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

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

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

Первая строка каждого набора входных данных содержит одно число $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — длину строки.

Вторая строка каждого набора входных данных содержит строку $$$s$$$. Гарантируется, что строка содержит только строчные буквы латинского алфавита.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

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

Пример
Входные данные
5
5
aaaaa
1
z
5
ababa
14
bcdaaaabcdaaaa
20
abcdefghijklmnopqrst
Выходные данные
5
1
9
50
210
Примечание

В первом наборе входных данных мы можем получить следующие строки: $$$a$$$, $$$aa$$$, $$$aaa$$$, $$$aaaa$$$, $$$aaaaa$$$.

В третьем наборе входных данных, например, слово $$$ba$$$ можно получить следующим образом:

  • удалить первый символ текущей строки $$$ababa$$$, получив $$$baba$$$;
  • удалить второй символ текущей строки $$$baba$$$, получив $$$bba$$$;
  • удалить второй символ текущей строки $$$bba$$$, получив $$$ba$$$.