Let us define two functions $*f*$ and $*g*$ on positive integer numbers.

You need to process $*Q*$ queries. In each query, you will be given three integers $*l*$, $*r*$ and $*k*$. You need to print the number of integers $*x*$ between $*l*$ and $*r*$ inclusive, such that $*g*(*x*) = *k*$.

Input

The first line of the input contains an integer $*Q*$ ($1 ≤ *Q* ≤ 2 × 10^{5}$) representing the number of queries.

$*Q*$ lines follow, each of which contains 3 integers $*l*$, $*r*$ and $*k*$ $(1 ≤ *l* ≤ *r* ≤ 10^{6}, 1 ≤ *k* ≤ 9)$.

Output

For each query, print a single line containing the answer for that query.

Note

In the first example:

• $*g*(33) = 9$ as $*g*(33) = *g*(3 × 3) = *g*(9) = 9$
• $*g*(47) = *g*(48) = *g*(60) = *g*(61) = 6$
• There are no such integers between $47$ and $55$.
• $*g*(4) = *g*(14) = *g*(22) = *g*(27) = *g*(39) = *g*(40) = *g*(41) = *g*(58) = 4$