Counting Good Substrings

Given a string S that consists only of the digits from 1 to 9, we call a string s good if there exist two non‐overlapping intervals \([l_1,r_1]\) and \([l_2,r_2]\) within s such that

$$1 \le l_1 \le r_1 < l_2 \le r_2 \le |s|$$

Let x be the integer formed by the digits in the first interval and y be the integer formed by the digits in the second interval. The string s is good if and only if \(x\) divides \(y\), i.e.,

$$x \mid y \quad\text{(which means } y \bmod x = 0\text{)}.$$

Now, given the string S, count how many substrings of S are good. Note that here substrings are contiguous segments of S and are not required to be distinct.

inputFormat

The input consists of a single line containing the string S, consisting solely of the digits 1,2,3,4,5,6,7,8,9.

outputFormat

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

sample

123

2