Рядок 20230322 можна змінити на 02320232, що є повторенням 0232 двічі.

Так само кажуть, що рядок, що складається з цифр, є щасливим, якщо його можна переставити у (або вже є) повторення деякого рядка двічі.

Вам дається рядок \(S\), що складається з цифр. Знайдіть кількість пар цілих чисел \((l,r)\), які задовольняють усі наступні умови.

• \(1≤l≤r≤∣S∣\). ( \(∣S∣\) – це довжина \(S\).)
• (Безперервний) підрядок, утворений символами з \(l\)-го по \(r\)-й рядка \(S\), є щасливим.

Обмеження

• \(S\) — це рядок, що складається з цифр, довжина яких становить від 1 до \(5×10^5\) включно.

Формат вхідних даних

Вхідний потік містить \(S\).

Формат вихідних даних

У вихідний потік виведіть відповідь.

Приклад вхідних даних

20230322

Приклад вихідних даних

4

Маємо \(S\)= 20230322.

Ось чотири пари цілих чисел \((l,r)\), які задовольняють умову: (1,6), (1,8), (2,7) і (7,8).

Приклад вхідних даних

0112223333444445555556666666777777778888888889999999999

Приклад вихідних даних

185

\(S\) може починатися з 0.

Приклад вхідних даних

3141592653589793238462643383279502884197169399375105820974944

Приклад вихідних даних

9