Clarke is a patient with multiple personality disorder. One day, Clarke turned into a researcher, did a research on digits.
He wants to know the number of positive integers which have a length in $[l, r]$ and are divisible by $7$ and the sum of any adjacent digits can not be $k$.
Input
The first line contains an integer $T(1 \le T \le 5)$, the number of the test cases.
Each test case contains three integers $l, r, k(1 \le l \le r \le 10^9, 0 \le k \le 18)$.
Output
Each test case print a line with a number, the answer modulo $10^9+7$.
Sample Input
2
1 2 5
2 3 5
Sample Output
13
125
Hint:
At the first sample there are 13 number $7,21,28,35,42,49,56,63,70,77,84,91,98$ satisfied.
