时空限制

1S/512M

题目描述

我们称一个整数 $x$ 是好数，当且仅当 $x$ 的每个数位中，出现次数最多的数字的次数与出现次数最少的数字（仅统计出现过的数字）的次数之间的差值不超过 $k$。

形式化地说，若 $x$ 的某些数位数字出现最多，出现次数为 $f_{\max}$，而某些数字出现最少，出现次数为 $f_{\min}$，则 $x$ 是好数当且仅当：

例如，当 $k = 1$ 时，$1277$ 是一个好数，因为 $f_{\max} = 2$ （数字 $7$ 出现了 $2$ 次），而 $f_{\min} = 1$ （数字 $1$ 和 数字 $2$ 均出现了 $1$ 次），$f_{\max} - f_{\min} = 1 \leq k$，故 $1277$ 是一个好数。

给定三个整数 $l$，$r$ 和 $k$，请你统计区间 $[l, r]$ 中好数的个数。

格式

输入格式

本题有多组测试数据。

第一行一个整数 $T$，表示测试数据组数。

接下来 $T$ 行，每行三个整数 $l, r, k$，含义如上所述。

输出格式

输出 $T$ 行，每行一个整数，表示对应查询中区间 $[l, r]$ 中好数的个数。

样例

样例输入 #1

1
1000 2000 1

样例输出 #1

964

数据规模

对于 $20\%$ 的数据， $1 \leq l \leq r \leq 10^5$。

对于 $100\%$ 的数据，$1 \leq T \leq 10$，$1 \leq l \leq r \leq 10^{18}$，$1 \leq k \leq 18$。