克拉克是一名人格分裂患者。某一天，克拉克变成了一个研究人员，在研究数字。 他想知道在所有长度在$[l, r]$之间的能被$7$整除且相邻数位之和不为$k$的正整数有多少个。
第一行一个整数$T(1 \le T \le 5)$，表示数据的组数。 每组数据只有一行三个整数$l, r, k(1 \le l \le r \le 10^9, 0 \le k \le 18)$。
每组数据输出一行一个数，表示答案。由于答案太大，你只需对$10^9+7$取模即可。
2 1 2 5 2 3 5
13 125
第一个样例有13个数满足，分别是：$7,21,28,35,42,49,56,63,70,77,84,91,98$