Count of Substrings Divisible by 4 or 5

Jimmy loves numbers and he is fascinated by their properties. One day, he scribbles down the number \(04320\) and starts doodling around it. He discovers that some of its contiguous substrings are multiples of \(4\) (for example, \(4\), \(04\), \(32\), \(432\), etc.) while others are multiples of \(5\) (for example, \(20\), \(320\), etc.).

The challenge is: Given a string of digits, count how many contiguous substrings represent a number that is a multiple of either \(4\) or \(5\). Note the following:

• The substring may start with a \(0\).
• Substrings that come from different positions are considered distinct even if they have the same value.
• If a substring is a multiple of both \(4\) and \(5\) (i.e. a multiple of \(20\)), it should be counted only once.

Hint: A number is divisible by \(4\) if its last two digits form a number divisible by \(4\) (or if it is a single digit, that digit is divisible by \(4\)). Similarly, a number is divisible by \(5\) if its last digit is \(0\) or \(5\). Use these properties to count the valid substrings efficiently.

inputFormat

The input consists of a single line containing a non-empty string of digits.

For example:

04320

outputFormat

Output a single integer representing the count of contiguous substrings that are divisible by \(4\) or \(5\) (each substring that satisfies the condition is counted only once even if it meets both criteria).

For example, for the input above the correct output is:

11

sample

04320

11