Given a nonempty subset $$$S$$$ of the integers, we call an element $$$x\in S$$$ stable if exactly two of the three values $$$\{x + 1, x + 2, x + 3\}$$$ are in $$$S$$$. Otherwise, we call $$$x\in S$$$ unstable.
Define a subset $$$S$$$ to be balanced if at most $$$2$$$ of its elements are unstable.
Given a set of distinct positive integers $$$A$$$, count the number of non-empty subsets of $$$A$$$ that are balanced. Since this number may be large, output it modulo $$$998\,244\,353$$$.
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.
The first line of each test case contains a single integer $$$n$$$ ($$$1\le n\le 2\cdot 10^5$$$) — the number of integers in $$$A$$$.
The second line contains $$$n$$$ integers $$$a_1 \lt a_2 \lt \ldots \lt a_n$$$ ($$$1 \le a_i \le 3\cdot n$$$) — the elements of $$$A$$$.
It is guaranteed that the sum of $$$n$$$ over all test cases is at most $$$2\cdot 10^5$$$.
For each test case, output a single integer: the number of non-empty subsets of $$$A$$$ that are balanced. Since this number may be large, output it modulo $$$998\,244\,353$$$.
441 2 3 4101 2 4 6 7 8 10 11 15 1661 2 3 15 17 1813
1466231
In the first example, the non-empty balanced subsets of $$$\{1, 2, 3, 4\}$$$ are (split on two lines for readability): $$$$$$\{1\}, \{2\}, \{3\}, \{4\}, \{1, 2\}, \{1, 3\}, \{1, 4\}, $$$$$$ $$$$$$\{2, 3\}, \{2, 4\}, \{3, 4\}, \{1, 2, 3\}, \{1, 2, 4\}, \{1, 3, 4\}, \{2, 3, 4\}.$$$$$$ Note that $$$S = \{1, 2, 3, 4\}$$$ is not balanced since all of $$$1, 3$$$, and $$$4$$$ are unstable. For example, $$$1$$$ is unstable since all of $$$2, 3$$$, and $$$4$$$ are also in $$$S$$$.
In the third example, one of the unbalanced subsets is $$$\{1, 2, 3, 18\}$$$ and one of the balanced subsets is $$$\{15, 17, 18 \}$$$.
| Codeforces Round 1133 (Div. 2) |
|---|
| Finished |
