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.
// stupid fking problem

import java.io.*;
import java.util.*;

public class tank {

    static final FastScanner fs = new FastScanner();

    static PrintWriter out = new PrintWriter(System.out);

    public static void main(String[] args) {
        int t = fs.nextInt();
        while(t-- > 0) run_case();

        out.close();
    }
    
    static void run_case() {
        int n = fs.nextInt();
        int[] a = fs.readArray(n);

        HashMap<Integer, Integer> hm = new HashMap<>();

        ruffleSort(a);

        boolean eq = true;

        int mx = a[n - 1], smx = a[0];

        hm.put(a[0], hm.getOrDefault(a[0], 0) + 1);

        for (int i = 1; i < n; i++) {
            if(a[i] - a[i - 1] > 1) {
                out.println(0);
                return;
            }

            if(a[i] < mx) smx = Math.max(smx, a[i]);

            hm.put(a[i], hm.getOrDefault(a[i], 0) + 1);

            if(a[i] != a[i - 1]) {
                eq = false;
            }
        }

        if(hm.get(mx) > 1) eq = true;

        long mod = 998244353, nf = 1;

        long[] pref = new long[n + 1];

        pref[0] = 1;

        for (int i = 1; i <= n; i++) {
            nf = (nf * i) % mod;
            pref[i] = nf;
        }

        if(eq) {
            out.println(nf);
        }else {
            long red = n - 1 - hm.get(smx), ans = 0;

            long[] fkthis = new long[n + 1];
            fkthis[0] = 1;

            fkthis[1] = red;

            for (int i = (int) (red - 1); i >= 1; i--) {
                fkthis[(int) (red - i + 1)] = (fkthis[(int) (red - i)] * i) % mod;
            }

            for (int i = 0; i <= red; i++) {
                ans = (ans + (pref[n - 1 - i] * fkthis[i]) % mod) % mod;
            }

            out.println((nf - ans + mod) % mod);
        }
    }

    static void ruffleSort(int[] a) {
        int n=a.length;
        Random r=new Random();
        for (int i=0; i<a.length; i++) {
            int oi=r.nextInt(n), temp=a[i];
            a[i]=a[oi];
            a[oi]=temp;
        }

        Arrays.sort(a);
    }

    static class FastScanner {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer("");
        String next() {
            while (!st.hasMoreTokens())
                try {
                    st=new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            return st.nextToken();
        }

        String nextLine(){
            try {
                return br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }

            return "";
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        int[] readArray(int n) {
            int[] a=new int[n];
            for (int i=0; i<n; i++) a[i]=nextInt();
            return a;
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }
    }
}