这个问题的简单版本和困难版本仅在 $$$n$$$ 的约束上有所不同。在简单版本中,所有测试用例的 $$$n^2$$$ 值之和不超过 $$$10^6$$$。此外,每个测试用例中的 $$$n$$$ 不超过 $$$1000$$$。
有 $$$2n$$$ 个灯泡排成一排。每个灯泡的颜色从 $$$1$$$ 到 $$$n$$$(每种颜色恰好有两个灯泡)。
最初,所有灯泡均关闭。您选择一组最初打开的灯泡 $$$S$$$。之后,您可以按任意顺序多次执行以下操作:
- 选择两个相同颜色的灯泡$$$i$$$和$$$j$$$,其中一个是亮着的,然后打开第二个;
- 选择三个灯泡 $$$i, j, k$$$,使得灯泡 $$$i$$$ 和 $$$k$$$ 都亮起并且颜色相同,灯泡 $$$j$$$ 位于它们之间 ($$$i < j < k$$$),然后打开灯泡 $$$j$$$。
您想要选择一组最初打开的灯泡 $$$S$$$,通过执行所描述的操作,您可以确保所有灯泡都打开。
计算两个数字:
- 您最初打开的 $$$S$$$ 集合的最小大小;
- 最小大小的集合 $$$S$$$ 的数量(以 $$$998244353$$$ 为模)。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。然后按照测试用例的描述进行操作。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 1000$$$) — 灯泡对的数量。
每个测试用例的第二行包含 $$$2n$$$ 整数 $$$c_1, c_2, \dots, c_{2n}$$$ ($$$1 \le c_i \le n$$$),其中 $$$c_i$$$ 是第 $$$i$$$ 个灯泡的颜色。对于从 $$$1$$$ 到 $$$n$$$ 的每种颜色,恰好有两个灯泡具有这种颜色。
对输入的附加约束:所有测试用例的 $$$n^2$$$ 值的总和不超过 $$$10^6$$$。
输出
对于每个测试用例,输出两个整数:
- 您最初打开的 $$$S$$$ 集合的最小大小;
- 最小大小的集合 $$$S$$$ 的数量(以 $$$998244353$$$ 为模)。
示例
输入 #1
4 2 2 2 1 1 2 1 2 2 1 2 1 2 1 2 5 3 4 4 5 3 1 1 5 2 2
输出 #1
2 4 1 2 1 4 2 8