以下题面由 AI 翻译。

问题描述

通常，中文版本的内容包含以下部分：

• 题目描述
• 输入格式
• 输出格式
• 样例数据
• 数据范围
• 提示

如果存在约束条件和提示部分，它们可能合并为一个部分， 如果有输入/输出示例，请保留它们原样，并保留所有围绕它们的注释。 优先使用字面翻译，但如果你有一个HTML文件，你可以将其重写为Markdown。

让我们称一个整数序列美丽，如果满足以下条件：

• 其长度至少为3；
• 对于除了第一个元素之外的每个元素，左边存在一个小于它的元素；
• 对于除了最后一个元素之外的每个元素，右边存在一个大于它的元素；

例如，[1, 4, 2, 4, 7]和[1, 2, 4, 8]是美丽的，但[1, 2]、[2, 2, 4]和[1, 3, 5, 3]不是。

回忆一下，子序列是从另一个序列中通过删除一些元素而得到的，而不改变剩余元素的顺序。

你被给定一个整数数组$a$，大小为$n$，其中每个元素都是1到3。你的任务是计算数组$a$中美丽子序列的数量。由于答案可能很大，请按模998244353输出。

输入格式

第一行包含一个整数$t$（$1 \le t \le 10^4$）——测试用例的数量。

每个测试用例的第一行包含一个整数$n$（$3 \le n \le 2 \cdot 10^5$）。

每个测试用例的第二行包含$n$个整数$a_1, a_2, \dots, a_n$（$1 \le a_i \le 3$）。

输入的额外约束：所有测试用例中$n$的总和不超过$2 \cdot 10^5$。

输出格式

对于每个测试用例，输出一行——数组$a$中美丽子序列的数量，按模998244353计算。

输入示例

1|2,3,6,7
4
7
3 2 1 2 2 1 3
4
3 1 2 2
3
1 2 3
9
1 2 3 2 1 3 2 2 3

输出示例

3
0
1
22

注意

在第一个示例中，以下子序列是美丽的：

• $[a_3, a_4, a_7]$;
• $[a_3, a_5, a_7]$;
• $[a_3, a_4, a_5, a_7]$.