TLE '17 Contest 8 P3 - Curious Numbers

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem type

Fax McClad is a deep thinker.

Fax McClad, Croneria's most curious bounty hunter, is interested certain numbers.

A number is called a palindrome if it is the same when read left-to-right or right-to-left. For example, 12321 is a palindrome, and 1234 is not. Leading zeroes are not part of a palindrome. For example, 3130 is not a palindrome.

Fax also loves the number K and any multiple of it.

Fax is interested in the palindromes that are divisible by K between M and N, inclusive. He will do this Q times. Can you tell him how many of these numbers there are?

Input Specification

The first line of input will contain Q (1 \le Q \le 10^5) and K (1 \le K \le 10^{10}).

The Q lines of input follow. Each line will contain M and N (1 \le M \le N \le 10^{10}).

For 20\% of the points, N,M,K,Q \le 10^3.

For an additional 30\% of the points, N,M,K \le 10^6, Q \le 10^3.

Output Specification

On separate lines, print the answer to each query.

Sample Input

2 2
10 50
100 300

Sample Output


Explanation for Sample Output

For the first query, 11, 22, 33, 44 are the only palindromes in between 10 and 50. Only 22 and 44 are divisible by 2.


There are no comments at the moment.