题目描述

Source: Codeforces Goodbye 2017 G. New Year and Original Order

LibreOJ 又锅了。

在锅了的 LibreOJ 中，一道题目的总得分通过如下方式计算：

1. 取出此题的所有提交记录，得到序列 A。

2. 对于 A 的每个元素，假设其得分为 $x$，对总得分的贡献为 $xf(x)$。

其中 $f(x)=\texttt{atoi(sort(itoa(x, b)), b)}$。

itoa(x, b) 表示将正整数 $x$ 以 $b$ 进制形式转换得到的字符串。

sort(s) 表示将字符串 $s$ 中的字符按照升序排序得到的字符串。

atoi(s, b) 表示将字符串 $s$ 以 $b$ 进制形式转换得到的正整数。

例如：
　itoa(184, 3) = "20211"
　sort("20211") = "01122"
　atoi("01122", 3) = 44
则当 $b=3$ 时 $f(184)=44$。

LibreOJ 的第 -1 题有着 $n$ 个提交记录，第 $i$ 个提交记录的得分为 $i$，请你求出第 -1 题的总得分。

形式化地说，你需要求出 $\displaystyle\sum_{i=1}^{n}if(i)$。

为了方便输出，你只需要求出答案对 $998,244,353$ 取模的结果即可。

输入格式

本题输入文件包含多组数据。

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

第二行一个正整数 $b$，意义见题目描述。

接下来每行表示一组数据。

每组数据一行一个以 $b$ 进制形式表示的正整数 $n$，意义见题目描述。

输出格式

对于每组数据，输出一行一个整数表示答案。

样例 1

input

3
10
5
10
100

output

55
295
221530

对于前两组数据，除了 $f(10)=1$ 之外，其它运算需要的 $f(x)=x$。

所以 $n=5$ 时答案为 $1^2+2^2+3^2+4^2+5^2=55$。

而 $n=10$ 时答案为 $1^2+2^2+\cdots+9^2+10=295$。

样例 2

input

2
2
111
1001010010100101010001100101101111010110001110

output

98
588970119

数据范围与提示

定义 $\mathrm{Len}=T+\sum\lfloor\log_b(n)\rfloor$。

对于所有测试点：$T\le 20$，$2\le b\le 10$，$n\le 10^{1000}$，$\mathrm{Len}\le 1000$。

每个测试点的具体限制见下表：

Author: PinkRabbit