description: Let's call a sequence of integers x_1, x_2, ..., x_k MEX-correct if for all i (1 ≤ i ≤ k) |x_i - \operatorname{MEX}(x_1, x_2, ..., x_i)| ≤ 1 holds. Where \operatorname{MEX}(x_1, ..., x_k) is the minimum non-negative integer that doesn't belong to the set x_1, ..., x_k. For example, \operatorname{MEX}(1, 0, 1, 3) = 2 and \operatorname{MEX}(2, 1, 5) = 0.
  
  You are given an array a consisting of n 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 [a_{i_1}, a_{i_2}, ..., a_{i_m}] meeting the constraints 1 ≤ i_1 < i_2 < ... < i_m ≤ n. If two different ways to choose the sequence of indices [i_1, i_2, ..., i_m] yield the same subsequence, the resulting subsequence should be counted twice (i. e. two subsequences are different if their sequences of indices [i_1, i_2, ..., i_m] are not the same).
  
  Input
  
  The first line contains a single integer t (1 ≤ t ≤ 10^5) — the number of test cases.
  
  The first line of each test case contains a single integer n (1 ≤ n ≤ 5 ⋅ 10^5).
  
  The second line contains n integers a_1, a_2, ..., a_n (0 ≤ a_i ≤ n).
  
  The sum of n over all test cases doesn't exceed 5 ⋅ 10^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. 
solution: // package c1613;
  
  import java.io.File;
  import java.lang.invoke.MethodHandles;
  import java.util.ArrayList;
  import java.util.Arrays;
  import java.util.Collection;
  import java.util.Iterator;
  import java.util.List;
  import java.util.Random;
  import java.util.Scanner;
  
  //
  // Educational Codeforces Round 118 (Rated for Div. 2) 2021-12-01 06:35
  // D. MEX Sequences
  // https://codeforces.com/contest/1613/problem/D
  // time limit per test 2 seconds; memory limit per test 256 megabytes
  //
  // public class Pseudo for "Source should satisfy regex [^{}]*public\s+(final)?\s*class\s+(\w+).*"
  // Let's call a sequence of integers x_1, x_2, ..., x_k if for all i (1 <= i <= k) |x_i -
  // \operatorname{MEX}(x_1, x_2, ..., x_i)| <= 1 holds. Where \operatorname{MEX}(x_1, ..., x_k) is
  // the minimum non-negative integer that doesn't belong to the set x_1, ..., x_k. For example,
  // \operatorname{MEX}(1, 0, 1, 3) = 2 and \operatorname{MEX}(2, 1, 5) = 0.
  //
  // You are given an array a consisting of n non-negative integers. Calculate the number of non-empty
  // 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 [a_{i_1}, a_{i_2}, ..., a_{i_m}] meeting the
  // constraints 1 <= i_1 < i_2 < ... < i_m <= n. If two different ways to choose the sequence of
  // indices [i_1, i_2, ..., i_m] yield the same subsequence, the resulting subsequence should be
  // counted twice (i.?e. two subsequences are different if their sequences of indices [i_1, i_2, ...,
  // i_m] are not the same).
  //
  // Input
  //
  // The first line contains a single integer t (1 <= t <= 10^5)-- the number of test cases.
  //
  // The first line of each test case contains a single integer n (1 <= n <= 5 * 10^5).
  //
  // The second line contains n integers a_1, a_2, ..., a_n (0 <= a_i <= n).
  //
  // The sum of n over all test cases doesn't exceed 5 * 10^5.
  //
  // Output
  //
  // For each test case, print a single integer-- the number of non-empty 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
  */
  //
  public class C1613D {
    static final int MOD = 998244353;
    static final Random RAND = new Random();
  
    static int solve(int[] a) {
      int n = a.length;
      int m = 0;
      for (int v : a) {
        m = Math.max(m, v);
      }
  
      // cp[i] is number of compact MEX-correct subsequences ends with i.
      // For examples: 0, 01, 001112
      long[] cp = new long[m+3];
  
      // ep[i] is number of escape MEX-correct subsequences with maximal value i but NO i-1.
      // such sequence must end with either i or i-2
      // For examples: 11, 002, 00222, 001122244, 020
      long[] ep = new long[m+3];
  
      long sum = 0;
      for (int v : a) {
        if (v == 0) {
          // 1. be a cp[0] sequence with itself
          // 2. join an existing cp[0] sequence and still be an cp[0]
          // 3. join ep[2] sequence and remain as ep[2] Example: 020
          sum += cp[0] + 1 + ep[2];
          cp[0] = (cp[0] + cp[0] + 1) % MOD;
          ep[2] = (ep[2] + ep[2]) % MOD;
        } else if (v == 1) {
          // 1. be an ep[1] sequence by itslef
          // 2. join an existing ep[1] sequence to remain as ep[1]
          // 3. join cp[1] sequence to remain as cp[1]
          // 4. join cp[0] sequence to become cp[1]
          // 5. join ep[3] sequence to remain as ep[3] Example: 0131
  
          sum += 1 + ep[1] + cp[1] + cp[0] + ep[3];
          ep[1] = (ep[1] + ep[1] + 1) % MOD;
          cp[1] = (cp[1] + cp[1] + cp[0]) % MOD;
          ep[3] = (ep[3] + ep[3]) % MOD;
        } else {
          // 1. join cp[v] sequence to remain as cp[v]
          // 2. join cp[v-1] sequence to become cp[v]
          // 3. join cp[v-2] sequence to become ep[v]
          // 4. join ep[v] sequence to remain as ep[v]
          // 5. join ep[v + 2] sequence to remain as ep[v+2] Example: 01242
          sum += cp[v] + cp[v-1] + cp[v-2] + ep[v] + ep[v+2];
          cp[v] = (cp[v] + cp[v] + cp[v-1]) % MOD;
          ep[v] = (ep[v] + ep[v] + cp[v-2]) % MOD;
          ep[v + 2] = (ep[v + 2] + ep[v + 2]) % MOD;
        }
        // System.out.format("  v:%d cp:%s ep:%s sum:%d\n", v, Arrays.toString(cp), Arrays.toString(ep), sum);
        sum %= MOD;
      }
      return (int) sum;
    }
  
    static long solveNaive(int[] a) {
      int n = a.length;
      List<Integer> nums = new ArrayList<>();
      long ans = 0;
      for (int i = 1; i < (1 << n); i++) {
        nums.clear();
        for (int j = 0; j < n; j++) {
          if ((i & (1 << j)) != 0) {
            nums.add(a[j]);
          }
        }
        if (isMexSeq(nums)) {
          ans++;
          System.out.format("  %3d %s\n", ans, join(nums));
        }
      }
      return ans;
    }
  
    public static String join(Collection<?> objs) {
      StringBuilder sb = new StringBuilder();
      Iterator<?> it = objs.iterator();
      boolean first = true;
      while (it.hasNext()) {
        if (!first) {
          sb.append(',');
        }
        sb.append(it.next().toString());
        first = false;
      }
      return sb.toString();
    }
  
    static boolean isMexSeq(List<Integer> nums) {
      int m = nums.size();
      boolean[] used = new boolean[m+1];
      int missed = 0;
      for (int v : nums) {
        if (v <= m) {
          used[v] = true;
        }
        while (used[missed]) {
          missed++;
        }
        if (Math.abs(v - missed) > 1) {
          return false;
        }
      }
      return true;
    }
  
    static void doTest() {
      int n = 10;
      int[] a = new int[n];
      for (int i = 0; i < n; i++) {
        a[i] = RAND.nextInt(6);
      }
      System.out.println(Arrays.toString(a));
      int ans = solve(a);
      System.out.println(ans);
      long exp = solveNaive(a);
      if (ans != exp) {
        System.out.println("expected " + exp);
      }
      System.exit(0);
    }
  
    public static void main(String[] args) {
      // doTest();
      Scanner in = getInputScanner();
      int T = in.nextInt();
      for (int t = 1; t <= T; t++) {
        int n = in.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
          a[i] = in.nextInt();
        }
        int ans = solve(a);
        System.out.println(ans);
      }
      in.close();
    }
  
    static Scanner getInputScanner() {
      try {
        final String USERDIR = System.getProperty("user.dir");
        final String CNAME = MethodHandles.lookup().lookupClass().getSimpleName();
        final File fin = new File(USERDIR + "/io/c" + CNAME.substring(1,5) + "/" + CNAME + ".in");
        return fin.exists() ? new Scanner(fin) : new Scanner(System.in);
      } catch (Exception e) {
        return new Scanner(System.in);
      }
    }
  }
  