Вам дана строка \(s\) длины \(n\). Определим две операции, которые можно применить к строке:
- удалить первый символ строки;
- удалить второй символ строки.
Ваша задача — найти количество различных непустых строк, которые можно получить, применяя заданные операции над исходной строкой любое количество раз (возможно, нулевое), в любом порядке.
Выходные данные
Для каждого набора входных данных выведите одно целое число: количество различных непустых строк, которые вы можете получить.
Примечание
В первом наборе входных данных мы можем получить следующие строки: \(a\), \(aa\), \(aaa\), \(aaaa\), \(aaaaa\).
В третьем наборе входных данных, например, слово \(ba\) можно получить следующим образом:
- удалить первый символ текущей строки \(ababa\), получив \(baba\);
- удалить второй символ текущей строки \(baba\), получив \(bba\);
- удалить второй символ текущей строки \(bba\), получив \(ba\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
5
aaaaa
1
z
5
ababa
14
bcdaaaabcdaaaa
20
abcdefghijklmnopqrst
|
5
1
9
50
210
|