题目描述

Cuber QQ 得到了一台很奇怪的打字机。

这台打字机上，数字键 0 和数字键 1 坏掉了，因此 Cuber QQ 不能直接打出任何包含数字 0 或数字 1 的正整数。我们称一个正整数是 可输入数 ，当且仅当它的十进制表示中不含数字 0 和数字 1。例如，2, 9, 234, 8888 是可输入数；10, 101, 1203, 2024 不是可输入数。

现在 Cuber QQ 想得到一个目标正整数 $n$。虽然不能直接输入 $n$，但他可以输入若干个可输入数，并用加号把它们相加。对于一个正整数 $k$，如果存在 $k$ 个可输入数 $a_1,a_2,\dots,a_k$，满足：$a_1+a_2+\cdots+a_k=n$ ，则称 $n$ 可以用 $k$ 个可输入数表示。

由于 Cuber QQ 不想敲太多数字，他想知道：

1. 表示 $n$ 所需的最小 $k$；

2. 在使用最小 $k$ 的情况下，有多少种不同的有序表达式。

两个表达式被认为不同，当且仅当存在某个位置 $i$，使得第 $i$ 个加数不同。例如，表达式 $22+78$ 和表达式 $78+22$ 被认为是两种不同的表达式。

由于方案数可能很大，你只需要输出方案数对 $998244353$ 取模后的结果。

可以证明，对于本题输入中的每个 $n$，最小 $k$ 一定不超过 $3$。

输入格式

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

接下来的 $T$ 行，每行一个整数 $n_i$，其中用 $|n_i|$ 表示 $n_i$ 的十进制表示长度。

输出格式

对于每个测试数据，输出一行两个整数 $k,c$。其中 $k$ 表示最少需要几个可输入数；$c$ 表示使用最小 $k$ 时的有序表达式数量，对 $998244353$ 取模后的结果。

样例

4
19
100
911
20

3 42
2 56
2 392
3 36

样例解释

对于 $19$，它不能表示成两个可输入数之和。

当使用 $3$ 个可输入数时，三个加数都只能是一位数。设它们分别为 $x,y,z$，则需要满足 $x+y+z=19,\quad 2\le x,y,z\le 9$ ，满足条件的有序三元组共有 $42$ 个。

数据规模与约定

对于所有测试数据，保证：$1\le T\le 10^5,2\le |n_i|,\quad\sum_{i=1}^{T}|n_i|\le 2\times 10^5$。每个 $n_i$ 满足：$n_i$ 是一个不含前导零的正整数；$n_i$ 至少包含一个数字 0 或数字 1。

原题链接

原题链接