众所周知，ddc 最擅长 Dynamic Programming。这段时间，ddc 非常喜欢研究数字的 LIS（最长上升子序列）。我们定义一个数的 LIS 长度是他各个数位组成的序列的 LIS，为了
更好的给 ddc 准备生日礼物小雅米想知道，在 [l,r][l, r][l,r] 内有多少数，他们的 LIS 为 kkk?
第一行输入一个整数 T(1≤T≤10000)T(1\leq T \leq 10000)T(1≤T≤10000)，表示数据组数。
接下来T行每行三个整数 l,r,k(1≤l≤r≤1018,0≤k≤1000)l, r, k(1 \leq l \leq r \leq 10^{18}, 0 \leq k \leq 1000)l,r,k(1≤l≤r≤1018,0≤k≤1000)。
对于每组测试数据输出一行一个整数，表示答案。
1 123 321 2
139
