Count Eights Recursively

Background

Congcong is learning recursion, and Dawei has assigned him an interesting digit counting task.

Problem Description

Given a non-negative integer $n$, compute recursively (no loops) the count of the occurrences of $8$ as a digit. Except that an $8$ with another $8$ immediately to its left counts double, so $8818$ yields $4$. Note that mod ($n \% 10$) by $10$ yields the rightmost digit ($126 \% 10$ is $6$), while divide ($n / 10$) by $10$ removes the rightmost digit ($126 / 10$ is $12$).

Input Format

Input is given from Standard Input in the following format.

$n$

Output Format

Output is printed to Standard Output in the following format.

The total count of occurrences of $8$.

Sample

8

1

818

2

8818

4

Sample Explanation

For input $8818$:

• The rightmost $8$ (units digit) has no $8$ to its left, counts as $1$.
• The digit $1$ does not count.
• The second $8$ from the left (hundreds digit) has an $8$ to its left (thousands digit), so it counts as $2$.
• The leftmost $8$ (thousands digit) has no digit to its left, counts as $1$. Total count is $1 + 0 + 2 + 1 = 4$.

Constraints

Time limit: 1 second, Memory limit: 1024 KiB