Hide

Problem L
Champernowne Count

The nth 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 (1n105) and k (1k109).

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
Hide

Please log in to submit a solution to this problem

Log in