### Problem Statement

The string `20230322` can be rearranged into `02320232`, which is a repetition of `0232` twice.  
Similarly, a string consisting of digits is said to be **happy** when it can be rearranged into (or already is) a repetition of some string twice.  
You are given a string $S$ consisting of digits. Find the number of pairs of integers $(l,r)$ satisfying all of the following conditions.

-   $1 \le l \le r \le |S|$. ($|S|$ is the length of $S$.)
-   The (contiguous) substring formed of the $l$-th through $r$-th characters of $S$ is happy.

### Input

The input is given from Standard Input in the following format:

```
$S$
```

### Output

Print an integer representing the answer.

### Constraints

-   $S$ is a string consisting of digits whose length is between $1$ and $5 \times 10^5$, inclusive.

4

We have S= 20230322.
Here are the four pairs of integers (l,r) that satisfy the condition: (1,6), (1,8), (2,7), and (7,8).

185

S may begin with 0.