X-liked Counting

David is alway fond of new kinds of numbers.

He defines a number $x-liked$ if any of its prefixes or suffixes can be divided by $x$. A prefix is a contiguous part which begins at the leftmost position of the number and ends at any position of the number, and a suffix is a contiguous part which begins at any position of the number and ends at the rightmost position of the number. For example, $12$ is a prefix of $123$ while $23$ is a suffix of it. The number itself can be a prefix or a suffix of itself.

Now David wants to know how many $x-liked$ integers there are in the range $[l,r]$. However, since David doesn't like the number $7$, he won't allow digit $7$ to occur in the numbers, so you don't need to count in numbers like $27$,$372$,$774$ etc. because they all have at least one digit equals to $7$. Please tell him how many $x-liked$ integers there are in the range $[l,r]$ with no digit equals to $7$.

The first line contains one integer $T$($1 \leq T \leq 10$) , the number of testcases.

For each testcase, there is one line which contains three non-negative integers, $l$,$r$ and $x$.

$1 \leq l \leq r \leq 10^{18}$
$1 \leq x \leq 500$

For each testcase, output one number in one line, how many $x-liked$ integers there are in the range $[l,r]$ with no digit equals to $7$.

1
11 20 4

5

In the sample, there are five valid integers, 12(12 can be divided by 4), 14(4 can be divided by 4), 16(16 can be divided by 4), 18(8 can be divided by 4), 20(20 and 0 both can be divided by 4).

2021“MINIEYE杯”中国大学生算法设计超级联赛（8）