7056：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$.