The ~K~ is a red herring and should not add any additional difficulty to this problem.

For the first ~20\%~ of the points, for every query, we check all numbers from ~M~ to ~N~ to see if they are palindromes and divisible by ~K~. An easy way to check if a number is a palindrome is to reverse the number using multiplication and mod by ~10~.

Time Complexity: ~\mathcal{O}(\max(N)Q)~

For the next ~30\%~ of the points, we should first precompute whether or not each number from ~1~ to ~10^6~ is a palindrome divisible by ~K~. Note that there are only approximately ~10^3~ palindromes in this range. Thus, for every query, we iterate through all of the palindromes and count those that are in between ~M~ and ~N~ and divisible by ~K~.

Time Complexity: ~\mathcal{O}(\sqrt{\max(N)}Q+\max(N))~

For full points, we generate all palindromes efficiently. Start with all one and two digit palindromes, including 0 and 00. Then, for each existing palindrome, add digits 0 through 9 to the front and end to create palindromes with two more digits. Repeat until palindromes of length ~10~ have been generated. Finally, remove all palindromes that end with 0 (as they must begin with 0) or are not divisible by ~K~.

Next, we sort these palindromes, and we can answer the queries using binary search. Note that it is possible to generate palindromes in order, ridding the need to sort.

Time Complexity: ~\mathcal{O}(Q\log\sqrt{\max(N)}+\sqrt{\max(N)})~