m-Beautiful Numbers

An m-Beautiful Number is a number which is divisible by $m$ and the sum of the digits is also divisible by $m$. For example, $268$ is a 4-Beautiful Number, but $68$ and $26$ are not 4-Beautiful Number.

In this problem, you'll be given $3$ integers, $L$, $R$, and $m$, and you have to tell the number of m-Beautiful Numbers in between L and R (inclusive) . As the answer can be very large, you have to print it modulo $10^9 + 7$.

Input

The first line of the input will contain a number $T$ ($1 ≤ T ≤ 10^5$), number of test cases to follow. Next $T$ lines will contain $3$ integers $L$, $R$ ($1 ≤ L ≤ R ≤ 10^{50}$), and $m$ ($1 ≤ m ≤ 50$) each as stated in description.

Output

For each case, you have to print the number of m-Beautiful Numbers in between $L$ and $R$ (inclusive) modulo $10^9 + 7$.

Sample

Input	Output
2 1 20 3 1 20 4	6 2
3-Beautiful Numbers between $1$ to $20$: $3$, $6$, $9$, $12$, $15$, and $18$. 4-Beautiful Numbers between $1$ to $20$: $4$, and $8$.