Page Number

Interview

Time limit1sMemory limit1024 MB

Summary

Count the ways to split a digit string into two numbers i and n with no leading zeros and 1 <= i <= n.

Level: Easy3 of 10
Topics: String, Brute force
Solved: No attempts yet

Problem

The Stilian Chilingirov regional library in Shumen is running an inventory check. Each book has a library stamp on one of its pages. To speed up the work, the librarians print book information on a sheet of paper. Each book needs its own line reading "Страница i от n", where i is the page number with the library stamp and n is the total number of pages in the book.

The printer broke and printed only one long string of digits for each book. The librarians want to split these digits into two numbers, one for i and one for n. Count the number of ways to split the digit string so that it forms a valid "Страница i от n" label. Pages are numbered from 1 to n. The numbers i and n are written without leading zeros.

Input

A single string consisting only of digits is given on standard input.

Output

Print the number of ways the digits can be split to form a valid "Страница i от n" label.

Examples2

Example 1
Input
```
23507645
```
Expected output
```
3
```
Example 2
Input
```
0000080468
```
Expected output
```
0
```