题目描述

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

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

输入格式

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

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

输出格式

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

样例 1

input

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

output

9
28
44
58
70
80
88
94
98
100

若 $1 \leq x \leq 9$，整数 $x$ 是「$k$–美妙」的当且仅当 $x \leq k$； 若 $10 \leq x \leq 90$，整数 $x = 10a + b$ 是「$k$–美妙」的当且仅当 $|a - b| \leq k$，其中 $a, b$ 均为 $[0, 9]$ 内的整数； $100$ 是「$k$–美妙」的当且仅当 $k \geq 1$。

样例 2

input

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

output

135
380
573
721
830
906
955
983
996
1000

数据范围与提示

$1 \leq n \leq 5 \times 10^4$
$1 \leq l \leq r \leq 10^{18}$，$0 \leq k \leq 9$