← 返回题目列表

Codeforces · 924/F

F. 最小子集差异

中文机器翻译题面 查看原题

当且仅当可以将正整数 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。