human
Write me a Python program to print it modulo 998244353 given the following:
Can you solve the below in PYTHON3?
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.
assistant
#Here is Python program to print it modulo 998244353.

#!/usr/bin/env pypy3

from sys import stdin, stdout

def input(): return stdin.readline().strip()
def read_int_list(): return list(map(int, input().split()))
def read_int_tuple(): return tuple(map(int, input().split()))
def read_int(): return int(input())

MODULUS = 998244353

from itertools import chain, combinations, product

def subsets(iterable, low=0, high=None):
    "subsets([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    if high is None:
        high = len(s)
    return chain.from_iterable(combinations(s, r) for r in range(low, high+1))

### CODE HERE

def mex(A):
    sA = set(A)
    for i in range(0, 200):
        if i not in sA: return i
    assert(False)

def correct(seq):
    for i in range(len(seq)):
        if not (1 >= abs(seq[i] - mex(seq[0:i+1]))):
            return False
    return True

def subsequences(S):
    ret = []
    for indices in subsets(range(len(S))):
        ret += [[S[i] for i in indices]]
    return ret

from functools import lru_cache

def ans_bottom(S):
    i = len(S)
    sz = len(S)+9
    dp1 = [1]*(sz)
    dp2 = [1]*(sz)
    while i > 0:
        i -= 1
        dp1_add = dict()
        dp2_add = dict()

        if S[i]+1 < sz: dp1_add[S[i]+1] = dp1[S[i]+1]
        dp1_add[S[i]-1] = dp1[S[i]-1]

        if S[i]+1 < sz: dp2_add[S[i]+1] = dp2[S[i]+1]
        if S[i]+1 < sz: dp2_add[S[i]] = dp2[S[i]+1]
        dp2_add[S[i]-1] = dp1[S[i]-1]

        for k in dp1_add:
            dp1[k] += dp1_add[k]
            dp1[k] %= MODULUS
        for k in dp2_add:
            dp2[k] += dp2_add[k]
            dp2[k] %= MODULUS
    return (dp2[0]-1) % MODULUS

def ans(S):
    @lru_cache(None)
    def dp(mex_before, has_top, i):
        if i == len(S): return 1
        if has_top:
            ret = dp(mex_before, True, i+1)
            if S[i] in [mex_before-1, mex_before+1]: ret += dp(mex_before, True, i+1)
            return ret % MODULUS
        else:
            ret = dp(mex_before, False, i+1)
            if S[i]+1 == mex_before: ret +=...