Сегодня у повара Тонио важный день — в его родной город Морио приехал ревизор. Он доехал и до ресторана Тонио и заказал у него десерт. Тонио к такому повороту событий не был готов.
Как известно, десерт — это строка из строчных латинских символов. Тонио вспомнил общее правило десертов — строку \(s\) длины \(n\). Любой десерт \(t\) является вкусным, если количество вхождений строки \(t\) в строку \(s\) как подстроки делится нацело на длину \(t\).
Теперь Тонио хочет знать количество вкусных подстрок заготовки \(s\). Если подстрока встречается в строке \(s\) несколько раз, то в ответе нужно учесть все вхождения.
Выходные данные
В единственной строке выведите количество подстрок строки \(s\), являющихся вкусными десертами.
Примечание
В первом примере есть много вкусных подстрок — \(7\) из них это подстроки длины \(1\) (так как любое число делится на \(1\) нацело). Рассмотрим другие вкусные подстроки:
- «ab» встречается в \(s\) \(2\) раза, что делится на длину подстроки.
- «ba» также встречается \(2\) раза.
Следовательно ответ \(7 + 2 + 2 = 11\).
Обратите внимание, что в ответе учтены оба вхождения как «ab», так и «ba».
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
abacaba
|
11
|
|
2
|
8
abaababa
|
11
|
|
3
|
10
deadinside
|
12
|
|
4
|
5
aaaaa
|
12
|