Divisible - MarisaOJ: Marisa Online Judge

Divisible

Time limit: 2500 ms
Memory limit: 256 MB
You need to answer $T$ questions. Each question consists of two integers $a, b$. Count the number of integers in the range $[a, b]$ that are divisible by $k$, and the sum of their digits is also divisible by $k$. ### Input - The first line contains an integer $T$. - The next $T$ lines, each containing two integers $a, b$ representing a question. ### Output - For each question, print the number of satisfying numbers. ### Constraints - $1 \le T \le 200$. - $1 \le a, b \le 10^{12}$. - $1 \le k \le 10000$. ### Example Input: ``` 1 1 1000 4 ``` Output: ``` 64 ```