We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. All Contests
  2. HourRank 18
  3. Super Six Substrings

Super Six Substrings

David loves numeric strings. He considers a substring of a numeric sequence to be super if both of the following conditions are satisfied:

  • The substring's integer representation is divisible by .
  • It does not contain leading zeroes (e.g., 6 is super, but 06 is not).

In addition, he considers the one-character substring 0 to be super.

For example, has five super substrings: 6, 0, 6, 60, and 606.

Given , find and print the total number of super substrings in .

Note: The length of the numbers represented by and its substrings are likely to be outside of the bounds of what numeric data types can represent.

Input Format

A single numeric string denoting .

Constraints

Output Format

Print an integer denoting the number of super substrings.

Sample Input 0

4806

Sample Output 0

5

Explanation 0

The diagram below depicts the five super substrings of string :

image

Note that substrings 48, 480, and 4806 are super because they're divisible by and do not contain any leading zeroes, and the substring 0 is super because it consists of a single zero.