Page Number

Time limit2sMemory limit512 MB

Summary

Given a digit string, count the ways to split it into two positive integers i and n with no leading zeros, representing "Page i of n".

Level: Medium6 of 10
Topics: String, Implementation, Math, Brute force
Solved: No attempts yet

Problem

One day a robot librarian decided to do an inventory check. On one of the shelves, among copies of the 33rd edition of Cormen, it found a sheet from the statement of an ancient contest. The robot knows the format of statement layout, but this sheet left it puzzled.

Usually at the bottom of each statement page there is a line of the form <<Page $i$ of $n$ >>, where $i$ is the page number and $n$ is the total number of pages in the statement. On this sheet, however, there was only one long sequence of digits. Apparently the printer failed to print any character other than digits. So the numbers $i$ and $n$ merged into a single sequence of digits.

Now figuring out what number the found page had has become a big problem, and this problem can have many answers. The robot got curious how many answers there are, but since it was not made to solve such problems, it needs your help. Pages in the statement are numbered from 1 to $n$ , and the numbers $i$ and $n$ are written without leading zeros.

Determine how many correct lines of the form <<Page $i$ of $n$ >> there are such that deleting all characters except digits from them yields the string given in the input file.

Input

The input file contains a string consisting only of digits. The length of the string is between 1 and $200\,000$ , inclusive.

Output

Print the number of correct lines of the form <<Page $i$ of $n$ >> such that deleting all characters except digits from them yields the string given in the input file.

Hint

In the given example, the string can be interpreted in three ways:

<<Page 2 of 3507645>>
<<Page 23 of 507645>>
<<Page 2350 of 7645>>

Examples1

Example 1
Input
```
23507645
```
Expected output
```
3
```