You are given a range $L$ to $R$. You are required to find the number of k-special numbers in this range. A k-special number is a number whose all digits are a multiple of $k$.

For example:
26 is a 2-special number. Digits 2 and 6 are multiples of 2.
63 is a 3-special number. Digits 6 and 3 are multiples of 3.

Input format

• The first line contains $T$ denoting the number of test cases.
• Next $T$ lines contain integers $L\ R\ k$.

Output format

For each test case, print an integer in a separate line denoting the count of k-special integers in range $L$ to $R$ (both inclusive).

Constraints

$1 \le T \le 100000\\ 1 \le L \le R \le 10^{18}\\ 1 \le k \le 9$