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.util.*;
import java.lang.*;
import java.io.*;

public class Main
{
	PrintWriter out = new PrintWriter(System.out);
	BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer tok = new StringTokenizer("");
    String next() throws IOException {
        if (!tok.hasMoreTokens()) { tok = new StringTokenizer(in.readLine()); }
        return tok.nextToken();
    }
    int ni() throws IOException { return Integer.parseInt(next()); }
    long nl() throws IOException { return Long.parseLong(next()); }
    
    long mod=998244353;
    
    void solve() throws IOException {
        
        long[]F=new long[200001];
        F[0]=1;
        for (int i=1;i<200001;i++) F[i]=(F[i-1]*i)%mod;
        
        for (int tc=ni();tc>0;tc--) {
            int n=ni();
            int[]A=new int[n];
            int m1=0;
            int m2=0;
            for (int i=0;i<n;i++) {
                A[i]=ni();
                if (A[i]>m1) m1=A[i];
            }
            
            for (int i=0;i<n;i++) 
                if (A[i]>m2 && A[i]<m1) m2=A[i];
                
            int ctm1=0;
            int ctm2=0;
            for (int i=0;i<n;i++) {
                if (A[i]==m1) ctm1++;
                if (A[i]==m2) ctm2++;
            }
            
            if (ctm1>1) out.println(F[n]);
            else if (m1>m2+1) out.println(0);
            else {
                //out.println (ctm1+" "+ctm2);
                long ans=0;
                for (int i=1;i<n;i++) {
                    int behind=i-1;
                    //out.print(behind+" ");
                    if (behind<ctm2) ans=(ans+F[n-1])%mod;
                    else {
                        long a2=(F[behind]*mp(F[behind-ctm2],mod-2))%mod;
                        a2=(a2*F[n-1-ctm2])%mod;
                        ans=(ans+F[n-1]-a2)%mod;
                        //out.print(ans);
                    }
                    //out.println();
                }
                out.println(ans);
            }
            
        }
        out.flush();
    }
    
    int gcd(int a,int b) { return(b==0?a:gcd(b,a%b)); }
    long gcd(long a,long b) { return(b==0?a:gcd(b,a%b)); }
    long mp(long a,long p) { long r=1; while(p>0) { if ((p&1)==1) r=(r*a)%mod; p>>=1; a=(a*a)%mod; } return r; }
    
    public static void main(String[] args) throws IOException {
        new Main().solve();
    }
}