当且仅当可以将正整数 x 的十进制表示形式的数字多重集分成两个子集,使得一个子集中的数字总和与另一个子集中的数字总和之间的差值小于或等于 k 时,我们将正整数 x 称为 k 美整数。每个数字应该恰好属于分割后的一个子集。
有 n 个查询需要您解答。每个查询都用三个整数 l、r 和 k 来描述,这意味着系统会询问您在 l 和 r(含)之间有多少个整数 x 是 k 美丽的。
输入
第一行包含一个整数n (1 ≤ n ≤ 5·104),表示查询的数量。
接下来的 n 行中的每一行都描述一个查询,包含三个整数 l、r 和 k (1 ≤ l ≤ r ≤ 1018, 0 ≤ k ≤ 9)。
输出
对于每个查询,打印一个数字 - 查询的答案。
示例
输入 #1
10 1 100 0 1 100 1 1 100 2 1 100 3 1 100 4 1 100 5 1 100 6 1 100 7 1 100 8 1 100 9
输出 #1
9 28 44 58 70 80 88 94 98 100
输入 #2
10 1 1000 0 1 1000 1 1 1000 2 1 1000 3 1 1000 4 1 1000 5 1 1000 6 1 1000 7 1 1000 8 1 1000 9
输出 #2
135 380 573 721 830 906 955 983 996 1000
注意
如果 1 ≤ x ≤ 9,则整数 x 是 k-美的当且仅当 x ≤ k。
如果 10 ≤ x ≤ 99,则整数 x = 10a + b 是 k-美的当且仅当 |a - b| ≤ k,其中 a 和 b 是 0 到 9 之间的整数(含 0 和 9)。
100 是 k-美丽的当且仅当 k ≥ 1。