Хоч трішки поспати

Limits: 1 sec., 512 MiB

Зеник має рядок \(s\) з малих латинських букв. Він вирішив, що для кожного підрядка цього рядка повинен порахувати, скільки разів він присутній в рядку \(s\), і визначити, скільки підрядків присутні максимальну кількість разів. Рядок дуже великий, тому Зеник вже четверту ніч не заплющує своїх очей і вперто рахує кількості входжень підрядків в його рядок.

Марічка дуже переживає, що Зеник зовсім не спить і вирішила написати програму, котра миттєво знайде відповідь на питання, яке так бентежить Зеника. Оскільки ви пишете програми набагато краще за Марічку, дівчина просить допомоги у вас: за заданим рядком, знайдіть скільки його підрядків входять в нього максимальну кількість разів.

Input

Один рядок містить рядок \(s\).

Output

Одне число — кількість підрядків рядка \(s\), що мають в ньому найбільшу кількість повторів.

Constraints

\(1 \le |s| \le 10^6\),

\(s\) містить лише малі латинські літери.

Samples

Input (stdin) сopy	Output (stdout) сopy
abcd	10

Input (stdin) сopy	Output (stdout) сopy
abab	3

Input (stdin) сopy	Output (stdout) сopy
aaabb	1

Notes

У першому тесті всі підрядки унікальні, тобто присутні по одному разу.

У другому тесті по два повтори мають підрядки a, b та ab.

У третьому тесті найбільше повторів (три) має підрядок a.