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\)