Migrated from Lutece 2997 Interval Digits Sum

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

秋老师得到了一个优美度 $m$，他定义一个整数为优美的，当且仅当这个整数在十进制表示下所有数位中出现的数字不超过 $m$。例如当 $m=2$ 时，数字 $1, 23,6262, 5050$ 都是优美的，而数字 $123,3347$ 都是不优美的。

秋老师想知道在 $l,l+1,...,r$ 中所有优美的数之和为多少。由于这个数字很大，请你将答案对 $998244353$ 取模。

Input

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

接下来 $T$ 行，每行输入 $3$ 个整数 $l,r,m$ 分别表示区间左端点，区间右端点以及优美度。

Output

输出共 $T$ 行，每行一个整数表示该数据组下的优美数之和。

Samples

3
10 50 1
10 50 2
1 999 3

110
1230
499500

Constraints

$1\leq T \leq 65, 1\leq l\leq r \leq 10^{18}, 1\leq m \leq 10$

Note

对于第一组数据，只有 $11,22,33,44$ 为优美的，答案为 $11+22+33+44=110$

Resources

2023 UESTC ICPC Training for Search and Dynamic Programming