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 java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.HashMap;
import java.util.StringTokenizer;



public class JuryMeeting {

    static long mod=998244353;

    public static void main(String[] args) {

        FastScanner f = new FastScanner();
        PrintWriter p = new PrintWriter(System.out);
        long fac[]=new long[200005];
        fac[0]=fac[1]=1;
        for(int i=2;i<fac.length;i++){
            fac[i]=mul(i,fac[i-1]);
        }
        int t = f.nextInt();
        while (t-- > 0) {
            int n=f.nextInt();
            long max=Long.MIN_VALUE;
            HashMap<Long,Long> h=new HashMap<>();
            for(int i=0;i<n;i++){
                long curr=f.nextLong();
                if(h.containsKey(curr)){
                    h.put(curr,h.get(curr)+1);
                }else{
                    h.put(curr,(long)1);
                }
                max=Math.max(max,curr);
            }

            if(h.get(max)>1){
                p.println(fac[n]);
            }else if(h.get(max)==1){
                if(h.containsKey(max-1)==false){
                    p.println(0);
                }else{
                    long k=h.get(max-1);
                    long ans=sub(fac[n],div(fac[n],k+1));
                    p.println(ans);
                }
            }

        }
        p.close();

    }

//-----------------------------------------------------------------------------------------------------------------------------------------------------------------

    static class FastScanner {
        BufferedReader br;
        StringTokenizer st;

        public FastScanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

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

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

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

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

    static long add(long x,long y){
        x += y;
        if(x >= mod) return (x % mod);
        return x;
    }
    static long sub(long x, long y){
        x -= y;
        if(x < 0)   return (x + mod);
        return x;
    }
    static long mul(long x, long y){
        return (x * y) % mod;
    }
    static long bin_pow(long x,long p){
        if(p == 0)  return 1;
        if((p & 1)!=0)   return mul(x, bin_pow(x, p - 1));
        return bin_pow(mul(x,x), p / 2);
    }
    static long rev(long  x) {
        return bin_pow(x, mod - 2);
    }
    static long div(long x, long y){
        return mul(x, rev(y));
    }


    // will work till array size of 65537---fastest sorting time
//	static long[] radixSort(long[] f) {
//		return radixSort(f, f.length);
//	}
//
//	static long[] radixSort(long[] f, int n) {
//		long[] to = new long[n];
//		{
//			int[] b = new int[65537];
//			for (int i = 0; i < n; i++)
//				b[1 + (int) (f[i] & 0xffff)]++;
//			for (int i = 1; i <= 65536; i++)
//				b[i] += b[i - 1];
//			for (int i = 0; i < n; i++)
//				to[b[(int) (f[i] & 0xffff)]++] = f[i];
//			long[] d = f;
//			f = to;
//			to = d;
//		}
//		{
//			int[] b = new int[65537];
//			for (int i = 0; i < n; i++)
//				b[1 + (int) (f[i] >>> 16 & 0xffff)]++;
//			for (int i = 1; i <= 65536; i++)
//				b[i] += b[i - 1];
//			for (int i = 0; i < n; i++)
//				to[b[(int) (f[i] >>> 16 & 0xffff)]++] = f[i];
//			long[] d = f;
//			f = to;
//			to = d;
//		}
//		{
//			int[] b = new int[65537];
//			for (int i = 0; i < n; i++)
//				b[1 + (int) (f[i] >>> 32 & 0xffff)]++;
//			for (int i = 1; i <= 65536; i++)
//				b[i] += b[i - 1];
//			for (int i = 0; i < n; i++)
//				to[b[(int) (f[i] >>> 32 & 0xffff)]++] = f[i];
//			long[] d = f;
//			f = to;
//			to = d;
//		}
//		{
//			int[] b = new int[65537];
//			for (int i = 0; i < n; i++)
//				b[1 + (int) (f[i] >>> 48 & 0xffff)]++;
//			for (int i = 1; i <= 65536; i++)
//				b[i] += b[i - 1];
//			for (int i = 0; i < n; i++)
//				to[b[(int) (f[i] >>> 48 & 0xffff)]++] = f[i];
//			long[] d = f;
//			f = to;
//			to = d;
//		}
//		return f;
//	}

    // Function to sort an array using quick sort algorithm.
    static void quickSort(long arr[], int low, int high) {
        if (low < high) {
            int p = partition(arr, low, high);
            quickSort(arr, low, p - 1);
            quickSort(arr, p + 1, high);
        }
    }

    static int partition(long arr[], int low, int high) {
        long pivot = arr[high];
        int i = low - 1;
        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                i++;
                long temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        long temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;

        return i + 1;
    }

    /// Ceils
    static long ceil(long x, long m) {
        long res = x / m;
        if (x % m != 0) {
            res++;
        }
        return res;
    }

    // ------------------------------------------------------------------------------------------------
    // makes the prefix sum array
    static long[] prefixSum(long arr[], int n) {
        long psum[] = new long[n];
        psum[0] = arr[0];
        for (int i = 1; i < n; i++) {
            psum[i] = psum[i - 1] + arr[i];
        }
        return psum;
    }
    // ------------------------------------------------------------------------------------------------

    // makes the suffix sum array
    static long[] suffixSum(long arr[], int n) {
        long ssum[] = new long[n];
        ssum[n - 1] = arr[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            ssum[i] = ssum[i + 1] + arr[i];
        }
        return ssum;
    }

//------------------------------------------------------------------------------------------
    // BINARY EXPONENTIATION OF A NUMBER MODULO M FASTER METHOD WITHOUT RECURSIVE
    // OVERHEADS

    static long binPower(long a, long n, long m) {
        if (n == 0)
            return 1;
        long res = 1;
        while (n > 0) {
            if ((n & 1) != 0) {
                res *= a;
            }
            a *= a;
            n >>= 1;
        }
        return res;
    }

//-------------------------------------------------------------------------------------------

    // gcd
    static long gcd(long a, long b) {
        return b == 0 ? a : gcd(b, a % b);
    }

//------------------------------------------------------------------------------------------

    // lcm
    static long lcm(long a, long b) {
        return a / gcd(a, b) * b;
    }

    //------------------------------------------------------------------------------------------
    // BRIAN KERNINGHAM TO CHECK NUMBER OF SET BITS
    // O(LOGn)
    static int setBits(int n) {
        int count = 0;
        while (n > 0) {
            n = n & (n - 1);
            count++;
        }
        return count;
    }
//------------------------------------------------------------------------------------------

    //------------------------------------------------------------------------------------------
    // 0 based indexing
    static boolean KthBitSet(int n, int k) {
        int mask = 1;
        mask = mask <<= k;
        if ((mask & n) != 0)
            return true;
        else
            return false;
    }

//------------------------------------------------------------------------------------------

    // EXTENDED EUCLIDEAN THEOREM
    // TO REPRESENT GCD IN TERMS OF A AND B
    // gcd(a,b) = a.x + b.y where x and y are integers

    static long x = -1;
    static long y = -1;

    static long gcdxy(long a, long b) {
        if (b == 0) {
            x = 1;
            y = 0;
            return a;
        } else {
            long d = gcdxy(b, a % b);
            long x1 = y;
            long y1 = x - (a / b) * y;
            x = x1;
            y = y1;

            return d;
        }
    }

//-------------------------------------------------------------------------------------------------F
}
