Champernowne Count

Interview

Time limit1sMemory limit1024 MB

Summary

Count how many of the first n Champernowne words, the concatenations of 1 through m, are divisible by k.

Level: Easy3 of 10
Topics: Math, Implementation
Solved: No attempts yet

Problem

The $n$ th Champernowne word is formed by writing the first $n$ positive integers in order and concatenating them. 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 the count of the first $n$ Champernowne words divisible by $k$ .

Examples4

Example 1
Input
```
4 2
```
Expected output
```
2
```
Example 2
Input
```
100 7
```
Expected output
```
14
```
Example 3
Input
```
314 159
```
Expected output
```
4
```
Example 4
Input
```
100000 999809848
```
Expected output
```
1
```