Digits in Page Numbers

A printer numbers the pages of a book from 1 to n, in ordinary decimal with no leading zeros. Each page number is printed once.

Write count_digit(n, d) that returns how many times the single digit d is printed across all the page numbers from 1 to n.

Examples

count_digit(13, 1)     # returns 6
count_digit(100, 0)    # returns 11
count_digit(9, 0)      # returns 0
count_digit(999, 7)    # returns 300

For n = 13 and d = 1, the digit 1 is printed in 1, 10, 11 (twice), 12 and 13: six times. For d = 0 up to 100, it is printed once in each of 10, 20, ..., 90 and twice in 100, which makes 11.

Constraints

• 1 <= n <= 10^18, so there are far too many pages to go through one by one
• 0 <= d <= 9

Note

Zero is the tricky digit, because no page number starts with 0.