Problem Background

Wave, I was wrong, please come back!

Problem Description

Given a string \( s \) consisting only of digits \( 1, 2, 3, 4, 5, 6, 7, 8, 9 \), you need to select two disjoint intervals \([l_1, r_1]\) and \([l_2, r_2]\) where \(1 \le l_1 \le r_1 < l_2 \le r_2 \le |s|\). Let the number extracted from the interval \([l_1, r_1]\) be \( x \) and the number from the interval \([l_2, r_2]\) be \( y \). The requirement is that \( x \) divides \( y \). If such two disjoint intervals exist, we call the string \( s \) good. (Here, \( | \) denotes divisibility, meaning \( x \) is a factor of \( y \))

Now, given a string \( S \) consisting only of digits \( 1, 2, 3, 4, 5, 6, 7, 8, 9 \), query how many of its substrings are good. (Substrings are not required to be distinct)

Input Format

The input consists of a single line containing a string \( S \) consisting only of digits \( 1, 2, 3, 4, 5, 6, 7, 8, 9 \).

Output Format

Output a single positive integer representing the number of good substrings.

Sample Input and Output

Sample Input #1

327

Sample Output #1

1

Sample Input #2

114514

Sample Output #2

12

Notes

Sample 1 Explanation

There is only one good string 327. You can choose two disjoint intervals \([1, 1]\) and \([2, 3]\), where the extracted numbers are \( 3 \) and \( 27 \), respectively. Clearly, \( 3 \) is a factor of \( 27 \), so this string is good.

Other substrings like 3, 2, 7, 32, 27 are not good because no such two disjoint intervals exist.

Sample 2 Explanation

There are 12 good strings, including 114514, 11451, 1145, 114, 11, 14514, 1451, 145, 14, 4514, 514, 14. (Note that there are two 14s, but since they are in different positions, we consider them as two different substrings)

Data Range

For all test cases, it is guaranteed that \( 2 \le |S| \le 10^6 \).

见题面 Input 部分

见题面 Output 部分