Hide

Problem D
Champernowne Count

The $n$th Champernowne word is obtained by writing down the first $n$ positive integers and concatenating them together. For example, the 10th Champernowne word is “12345678910”.

Given two positive integers $n$ and $k$, count how many of the first $n$ Champernowne words are divisible by $k$.

Input

The single line of input contains two integers, $n$ $(1 \le n \le 10^5)$ and $k$ $(1 \le k \le 10^9)$.

Output

Output a single integer, which is a count of the first $n$ Champernowne words divisible by $k$.

Sample Input 1 Sample Output 1
4 2
2
Sample Input 2 Sample Output 2
100 7
14
Sample Input 3 Sample Output 3
314 159
4
Sample Input 4 Sample Output 4
100000 999809848
1

Please log in to submit a solution to this problem

Log in