#P18771. Mobile Game Development Lab

Mobile Game Development Lab

Mobile Game Development Lab

你正在开发一款使用特殊随机数生成器的手机游戏。生成器接受一个正整数 aa,它取决于运行游戏的移动设备。生成器把 aa 和 a+1a+1 的无前导零十进制表示中的全部数字写入同一个字符串,然后随机打乱这些数字,将所得字符串作为随机数字序列。

你知道MTS Web Services(MWS)是一家提供云、人工智能和平台解决方案的大型科技公司,也认识许多在该公司开发产品的前竞赛获奖选手。现在,你想评估生成器多频繁输出字符串 ss,以及游戏在相应手机上的表现。为此需要在大量移动设备上测试游戏,但预算无法支持这么多设备。MWS产品能帮助开发者应对许多挑战,这次也不例外:你决定使用面向iOS和Android网页界面及移动应用的测试工具MWS SunQ,在多种设备上测试游戏。

你相信MWS SunQ可以完整覆盖生成器的所有可能输入。不过,为了确认这一点,你首先需要计算:有多少个正整数 aa,使得在相应设备上运行上述操作后,有可能得到给定字符串 ss。答案可能很大,输出其对 998244353998244353 取模的结果。

数字可以任意打乱,因此这里只要求 aa 和 a+1a+1 的全部数字构成的多重集合与 ss 相同,不计算打乱排列本身的方案数。

输入格式

第一行一个整数 tt(1≤t≤1041\le t\le10^4),表示测试用例数。

接下来每个测试用例一行,包含一个仅由0到9组成的非空字符串 ss,长度不超过 10510^5。

同一个输入文件内,所有字符串的长度之和不超过 10610^6。

输出格式

对每个测试用例输出一行,表示符合条件的正整数 aa 的数量对 998244353998244353 取模的结果。

样例

输入:

2
2025
121342

输出:

0
2