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 bisect
import heapq
import math
import collections
import sys
import copy
from functools import reduce
import decimal
from io import BytesIO, IOBase
import os
import itertools
import functools
from types import GeneratorType

sys.setrecursionlimit(10 ** 9)
decimal.getcontext().rounding = decimal.ROUND_HALF_UP

graphDict = collections.defaultdict

queue = collections.deque


################## pypy deep recursion handling ##############
# Author = @pajenegod
def bootstrap(f, stack=[]):
    def wrappedfunc(*args, **kwargs):
        to = f(*args, **kwargs)
        if stack:
            return to
        else:
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        return to
                    to = stack[-1].send(to)

    return wrappedfunc


################## Graphs ###################
class Graphs:
    def __init__(self):
        self.graph = graphDict(set)

    def add_edge(self, u, v):
        self.graph[u].add(v)
        self.graph[v].add(u)

    def dfs_utility(self, nodes, visited_nodes):
        visited_nodes.add(nodes)
        for neighbour in self.graph[nodes]:
            if neighbour not in visited_nodes:
                self.dfs_utility(neighbour, visited_nodes)

    def dfs(self, node):
        Visited = set()
        self.dfs_utility(i, Visited)

    def bfs(self, node, f_node):
        count = float("inf")
        visited = set()
        level = 0
        if node not in visited:
            queue.append([node, level])
            visited.add(node)
        flag = 0
        while queue:
            parent = queue.popleft()
            if parent[0] == f_node:
                flag = 1
                count = min(count, parent[1])
            level = parent[1] + 1
            for item in self.graph[parent[0]]:
                if item not in visited:
                    queue.append([item, level])
                    visited.add(item)
        return count if flag else -1


################### Tree Implementaion ##############
class Tree:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None


def inorder(node, lis):
    if node:
        inorder(node.left, lis)
        lis.append(node.data)
        inorder(node.right, lis)
    return lis


def leaf_node_sum(root):
    if root is None:
        return 0
    if root.left is None and root.right is None:
        return root.data
    return leaf_node_sum(root.left) + leaf_node_sum(root.right)


def hight(root):
    if root is None:
        return -1
    if root.left is None and root.right is None:
        return 0
    return max(hight(root.left), hight(root.right)) + 1


################## Union Find #######################
class UF:
    def __init__(self, N):
        self._id = list(range(N))
        self._count = N
        self._rank = [0] * N

    def find(self, p):
        id = self._id
        while p != id[p]:
            p = id[p] = id[id[p]]  # Path compression using halving.
        return p

    def count(self):
        return self._count

    def connected(self, p, q):
        return self.find(p) == self.find(q)

    def union(self, p, q):
        id = self._id
        rank = self._rank
        i = self.find(p)
        j = self.find(q)
        if i == j:
            return
        self._count -= 1
        if rank[i] < rank[j]:
            id[i] = j
        elif rank[i] > rank[j]:
            id[j] = i
        else:
            id[j] = i
            rank[i] += 1

    def __str__(self):
        """String representation of the union find object."""
        return " ".join([str(x) for x in self._id])

    def __repr__(self):
        """Representation of the union find object."""
        return "UF(" + str(self) + ")"


#################################################

def rounding(n):
    return int(decimal.Decimal(f'{n}').to_integral_value())


def factors(n):
    return set(reduce(list.__add__,
                      ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0), []))


def p_sum(array):
    return list(itertools.accumulate(array))


def diophantine(a: int, b: int, c: int):
    d, x, y = extended_gcd(a, b)
    r = c // d
    return r * x, r * y


@bootstrap
def extended_gcd(a: int, b: int):
    if b == 0:
        d, x, y = a, 1, 0
    else:
        (d, p, q) = yield extended_gcd(b, a % b)
        x = q
        y = p - q * (a // b)

    yield d, x, y


################################ <fast I/O> ###########################################
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, **kwargs):
        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)


#############################################<I/O Region >##############################################


def inp():
    return sys.stdin.readline().strip()


def map_inp(v_type):
    return map(v_type, inp().split())


def list_inp(v_type):
    return list(map_inp(v_type))


######################################## Solution ####################################


mod = 998244353
for _ in range(int(inp())):
    n = int(inp())
    arr = list_inp(int)
    arr.sort(reverse=True)
    if arr[0] - arr[1] > 1:
        print(0)
    else:
        dic = collections.Counter(arr)
        if dic[arr[0]] > 1:
            tmp = 1
            for i in range(2, n + 1):
                tmp *= i
                tmp %= mod
            print(tmp % mod)
        else:
            l = dic[arr[1]]
            tmp = 1
            for i in range(2, n + 1):
                tmp *= i
                tmp %= mod
            tmp *= pow(l + 1, -1, mod)
            tmp *= pow(l, 1, mod)
            print(tmp % mod)
