Problem Description

给定一个长度为$ n $的数字串$ s $， 你可以在任何缝隙中添加一个$*$，来切割这个数字串。

数据保证$ s[i] \neq 0 $

举个例子， $ 1234 $可以被分割成$ 12*34 $ 或者是 $ 1 * 234 $ 或者是 $ 1 * 2 * 3 * 4 $

当然你也可以不分割， 那就是$ 1234 $

定义串的价值是他做运算之后的结果， 比如 $ 12*34 $的价值为$ 408 $， $1234$的价值为$ 1234 $

求所有可能的结果的价值之和， 答案对998244353取模

Input

本题有多组数据， 第一行一个整数 $ T $描述数据组数

$ T \leq 10^6 $

接下来$ T $行， 每行一个数字串$ s $

题目保证 $ \sum |S| \leq 2 \times 10^6, |S| \leq 10^6$

Output

$ T $ 行， 每行输出一个整数用来描述可能结果的价值之和

3
234
5915
998244353

418
17800
258280134

Hint

$234$可以这么分割

$ 234, 2\*34, 23\*4, 2\*3\*4 $

价值分别为
$234$, $68$, $92$, $24$

所以答案为418