n people gathered to hold a jury meeting of the upcoming competition, the i-th member of the jury came up with a_i tasks, which they want to share with each other.

First, the jury decides on the order which they will follow while describing the tasks. Let that be a permutation p of numbers from 1 to n (an array of size n where each integer from 1 to n occurs exactly once).

Then the discussion goes as follows:

  * If a jury member p_1 has some tasks left to tell, then they tell one task to others. Otherwise, they are skipped. 
  * If a jury member p_2 has some tasks left to tell, then they tell one task to others. Otherwise, they are skipped. 
  * ... 
  * If a jury member p_n has some tasks left to tell, then they tell one task to others. Otherwise, they are skipped. 
  * If there are still members with tasks left, then the process repeats from the start. Otherwise, the discussion ends. 



A permutation p is nice if none of the jury members tell two or more of their own tasks in a row. 

Count the number of nice permutations. The answer may be really large, so print it modulo 998 244 353.

Input

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

The first line of the test case contains a single integer n (2 ≤ n ≤ 2 ⋅ 10^5) — number of jury members.

The second line contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ 10^9) — the number of problems that the i-th member of the jury came up with.

The sum of n over all test cases does not exceed 2 ⋅ 10^5.

Output

For each test case, print one integer — the number of nice permutations, taken modulo 998 244 353.

Example

Input


4
2
1 2
3
5 5 5
4
1 3 3 7
6
3 4 2 1 3 3


Output


1
6
0
540

Note

Explanation of the first test case from the example:

There are two possible permutations, p = [1, 2] and p = [2, 1]. For p = [1, 2], the process is the following:

  1. the first jury member tells a task; 
  2. the second jury member tells a task; 
  3. the first jury member doesn't have any tasks left to tell, so they are skipped; 
  4. the second jury member tells a task. 



So, the second jury member has told two tasks in a row (in succession), so the permutation is not nice.

For p = [2, 1], the process is the following:

  1. the second jury member tells a task; 
  2. the first jury member tells a task; 
  3. the second jury member tells a task. 



So, this permutation is nice.
import os
import sys
from io import BytesIO, IOBase
from collections import Counter
import math as mt

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)


def gcd(a, b):
    if a == 0:
        return b
    return gcd(b % a, a)


def lcm(a, b):
    return (a * b) / gcd(a, b)


mod = 998244353


def power(k, n):
    if n == 0:
        return 1
    if n % 2:
        return (power(k, n - 1) * k) % mod
    t = power(k, n // 2)
    return (t * t) % mod


def totalPrimeFactors(n):
    count = 0
    if (n % 2) == 0:
        count += 1
        while (n % 2) == 0:
            n //= 2

    i = 3
    while i * i <= n:
        if (n % i) == 0:
            count += 1
            while (n % i) == 0:
                n //= i
        i += 2
    if n > 2:
        count += 1
    return count


# #MAXN = int(1e7 + 1)
# # spf = [0 for i in range(MAXN)]
#
#
# def sieve():
#     spf[1] = 1
#     for i in range(2, MAXN):
#         spf[i] = i
#     for i in range(4, MAXN, 2):
#         spf[i] = 2
#
#     for i in range(3, mt.ceil(mt.sqrt(MAXN))):
#         if (spf[i] == i):
#             for j in range(i * i, MAXN, i):
#                 if (spf[j] == j):
#                     spf[j] = i
#
#
# def getFactorization(x):
#     ret = 0
#     while (x != 1):
#         k = spf[x]
#         ret += 1
#         # ret.add(spf[x])
#         while x % k == 0:
#             x //= k
#
#     return ret


# Driver code

# precalculating Smallest Prime Factor
# sieve()

N = 200001

factorialNumInverse = [-1] * (N + 1)

naturalNumInverse = [-1] * (N + 1)

fact = [1] * (N + 1)

def InverseofNumber(p):
    naturalNumInverse[0] = naturalNumInverse[1] = 1
    for i in range(2, N + 1, 1):
        naturalNumInverse[i] = (naturalNumInverse[p % i] *
                                (p - int(p / i)) % p)

def InverseofFactorial(p):
    factorialNumInverse[0] = factorialNumInverse[1] = 1
    for i in range(2, N + 1, 1):
        factorialNumInverse[i] = (naturalNumInverse[i] *
                                  factorialNumInverse[i - 1]) % p


def ncr(n, r):
    p=mod
    ans = ((fact[n] * factorialNumInverse[r]) % p *
           factorialNumInverse[n - r]) % p
    return ans

def main():
    InverseofNumber(mod)
    InverseofFactorial(mod)
    #fact = [1 for i in range(200001)]
    for i in range(1, N):
        fact[i] = (fact[i - 1] * i) % mod
    for _ in range(int(input())):
        n = int(input())
        a = list(map(int, input().split()))
        a.sort()
        maxx = a[-1]
        smax = -1
        for i in range(n - 1, -1, -1):
            if a[i] < maxx:
                smax = a[i]
                break
        if smax == -1 or a.count(maxx)>1:
            print(fact[n])
        elif a[-1]-a[-2] >= 2:
            print(0)
        else:
            s = a.count(maxx)
            m = a.count(smax)
            ans = (fact[m + s] * ncr(n, m + s)) % mod
            for i in range(m - 1, n-s):
                t = (ncr(i, m - 1) * (ncr(n - (i + 1), s))) % mod
                t = (t * fact[m]) % mod
                t = (t * fact[s]) % mod
                ans -= t
                ans = (ans + mod) % mod
            ans = (ans * fact[n - m - s]) % mod
            print(ans)

        # = map(int,input().split())

    return


if __name__ == "__main__":
    main()
