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$.
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)$.
Each test case print a line with a number, the answer modulo $10^9+7$.