Fax McClad is a deep thinker.

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

A number is called a palindrome if it is the same when read left-to-right or right-to-left. For example, ~12\,321~ is a palindrome, and ~1\,234~ is not. Leading zeroes are not part of a palindrome. For example, ~3\,130~ 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

2
10

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~.