#6372. 「VK Cup 2018 Round 2」最小子集差

内存限制:256 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: cyand1317

题目描述

我们称一个正整数 xxx 是「kkk–美妙」的,当且仅当存在一种方式将 xxx 的十进制表示中所有数码所组成的可重集拆分成两个子集,使得二者各自的元素之和的差值不大于 kkkxxx 十进制表示的每一个数码应出现在恰好一个子集中。

请解决 nnn 个询问,其中每一个形如 (l,r,k)(l, r, k)(l,r,k),询问 [l,r][l, r][l,r] 范围内「kkk–美妙」的整数个数。

输入格式

输入的第一行包含一个正整数 nnn —— 询问的数目。

接下来 nnn 行每行包含三个空格分隔的整数 l,r,kl, r, kl,r,k —— 询问 [l,r][l, r][l,r] 范围内「kkk–美妙」的整数个数。

输出格式

对于每个询问输出一行 —— 包含一个整数表示其答案。

样例

样例输入 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

样例解释 1

1≤x≤91 \leq x \leq 91x9,整数 xxx 是「kkk–美妙」的当且仅当 x≤kx \leq kxk
10≤x≤9010 \leq x \leq 9010x90,整数 x=10a+bx = 10a + bx=10a+b 是「kkk–美妙」的当且仅当 ∣a−b∣≤k|a - b| \leq kabk,其中 a,ba, ba,b 均为 [0,9][0, 9][0,9] 内的整数;
100100100 是「kkk–美妙」的当且仅当 k≥1k \geq 1k1

样例输入 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≤n≤5×1041 \leq n \leq 5 \times 10^41n5×104
1≤l≤r≤10181 \leq l \leq r \leq 10^{18}1lr10180≤k≤90 \leq k \leq 90k9