该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

首位校验

题目描述

给你一个只包含数字的字符串 $s$。

你需要把它切成若干个连续的段。每一段都必须满足：

这一段的第一个数字，等于这一段所有数字之和的个位数。

例如，246 是合法的一段，因为 $2+4+6=12$，和的个位数是 $2$，正好等于第一个数字 $2$。

你需要求：

1. 最少要切成多少段；
2. 在段数最少的情况下，有多少种不同的切法。

答案对 $998244353$ 取模。

两个切法不同，当且仅当至少有一个切开的位置不同。

输入格式

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

对于每组测试数据：

第一行输入一个整数 $n$。

第二行输入一个长度为 $n$ 的数字串 $s$。

数据范围

对于所有测试数据，保证：

字符串 $s$ 仅由字符 0 到 9 组成。

注意：单个数字本身一定是合法校验块，因此答案一定存在。

输出格式

对于每组测试数据，输出一行两个整数，分别表示最少块数和最优切分方案数。

输入输出样例 #1

输入 #1

4
3
120
4
0000
10
1234567890
8
31415926

输出 #1

2 1
1 1
4 2
3 1

说明/提示

对于 120，唯一的最优切分是：

1 | 20

对于 0000，整个串 0000 是一个合法校验块，因此最少只需要切成 $1$ 块。

对于 1234567890，有两种最优切分：

1 | 2 | 345678 | 90
123456 | 7 | 8 | 90

对于 31415926，唯一的最优切分是：

314159 | 2 | 6