CodeForces-Educational Codeforces Round 118

Let’s call a sequence of integers 𝑥1,𝑥2,…,𝑥𝑘 MEX-correct if for all 𝑖 (1≤𝑖≤𝑘) |𝑥𝑖−MEX(𝑥1,𝑥2,…,𝑥𝑖)|≤1 holds. Where MEX(𝑥1,…,𝑥𝑘) is the minimum non-negative integer that doesn’t belong to the set 𝑥1,…,𝑥𝑘. For example, MEX(1,0,1,3)=2 and MEX(2,1,5)=0.

You are given an array 𝑎 consisting of 𝑛 non-negative integers. Calculate the number of non-empty MEX-correct subsequences of a given array. The number of subsequences can be very large, so print it modulo 998244353.

Note: a subsequence of an array 𝑎a is a sequence [𝑎𝑖1,𝑎𝑖2,…,𝑎𝑖𝑚] meeting the constraints 1≤𝑖1<𝑖2<⋯<𝑖𝑚≤𝑛. If two different ways to choose the sequence of indices [𝑖1,𝑖2,…,𝑖𝑚] yield the same subsequence, the resulting subsequence should be counted twice (i. e. two subsequences are different if their sequences of indices [𝑖1,𝑖2,…,𝑖𝑚] are not the same).

Input

The first line contains a single integer 𝑡t ($1≤𝑡≤10^5$) — the number of test cases.

The first line of each test case contains a single integer 𝑛n ($1≤𝑛≤5\times10^5$).

The second line contains 𝑛 integers 𝑎1,𝑎2,…,𝑎𝑛 ($0≤𝑎𝑖≤𝑛$).

The sum of 𝑛 over all test cases doesn’t exceed $5\times10^5$.

Output

For each test case, print a single integer — the number of non-empty MEX-correct subsequences of a given array, taken modulo 998244353.

Example

input

4
3
0 2 1
2
1 0
5
0 0 0 0 0
4
0 1 2 3

output

4
2
31
7

Note

In the first example, the valid subsequences are [0], [1], [0,1] and [0,2].

In the second example, the valid subsequences are [0] and [1].

In the third example, any non-empty subsequence is valid.

Code

/**
 *    author:  subobo
 *    created: 2.12.2021
**/
#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  constexpr long long mod = 998244353;
  auto Add = [&](long long &a, long long b) {
    a += b;
    a %= mod;
  };
  int tt;
  cin >> tt;
  while (tt--) {
    int n;
    cin >> n;
    vector<vector<long long>> dp(n + 3, vector<long long>(3));
    for (int i = 0; i < n; ++i) {
      int a;
      cin >> a;
      // <case #1>0 0 0 0 1 1 1 2 2...
      // <case #2>0 0 1 1 3 3 3 1 3 1 3...

      // dp[i][0]: increasing and from the same number
      // dp[i][1]: 1 -> 3
      // dp[i][2]: 3 -> 1

      // choose or not choose
      Add(dp[a][0], dp[a][0]);
      Add(dp[a][1], dp[a][1]);
      Add(dp[a][2], dp[a][2]);

      if (a == 0) {
        // nul -> 0
        Add(dp[a][0], 1);
      }
      if (a) {
        // <case #1>
        Add(dp[a][0], dp[a - 1][0]);
      }
      if (a == 1) {
        // 3 -> 1
        Add(dp[a][1], 1);
      }
      if (a > 1) {
        // 3 -> 1
        Add(dp[a][1], dp[a - 2][0]);
        Add(dp[a][1], dp[a - 2][2]);
      }
      if (a + 2 <= n) {
        // 1 -> 3
        Add(dp[a][2], dp[a + 2][1]);
      }
    }
    long long res = 0;
    for (int i = 0; i <= n; ++i) {
      for (int j = 0; j < 3; ++j) {
        Add(res, dp[i][j]);
      }
    }
    cout << res % mod << '\n';
  }
  return 0;
}