Divisible - MarisaOJ: Marisa Online Judge

You need to answer

T

$T$ questions. Each question consists of two integers

a, b

$a, b$ . Count the number of integers in the range

[a, b]

$[a, b]$ that are divisible by

k

$k$ , and the sum of their digits is also divisible by

k

$k$ . ### Input - The first line contains an integer

T

$T$ . - The next

T

$T$ lines, each containing two integers

a, b

$a, b$ representing a question. ### Output - For each question, print the number of satisfying numbers. ### Constraints -

1 \leq T \leq 200

$1 \le T \le 200$ . -

1 \leq a, b \leq 10^{12}

$1 \le a, b \le 10^{12}$ . -

1 \leq k \leq 10000

$1 \le k \le 10000$ . ### Example Input:

1110004

$1 1 1000 4$

Output:

64

$64$

Topic

Dynamic Programming

Rating

1400

Solution (0)

Solution