Rhezo has a complicated function F whose value he needs to find given the parameters \(L, R\) and K. The function F is defined as below:

int F (int L, int R, int K) :
    ANS = 0
    For all subset of numbers S formed from numbers in range [L, R]:
        if S is not empty:
            //denote by SIZE the number of elements in S
            SET X //consists of unique elements only
            SUM = 0
            for all elements E in S:
                X.insert(sum of digits of E)
                SUM += sum of digits of E
            //denote by set_size the number of elements in X
            if set_size == SIZE and SUM >= K:
                ANS++
    return ANS%1000000007

Input:

First line of input contains a single integer T denoting the number of test cases. Each of the next T lines contain 3 integers \(L, R\) and K.

Output:

For each test case, find the value of \(F(L, R, K)\).

Constraints:

\(1 \le T \le 10\)

\(1 \le L \le R \le 10^{18}\)

\(1 \le K \le 13000\)