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.io.*;
public class Sol{
 
/*   
->check n=1, int overflow , array bounds , all possibilites(dont stuck on 1 approach)
->Problem = Observation(constraints(m<=n/3 or k<=min(100,n)) 
           + Thinking + Technique (seg_tree,binary lift,rmq,bipart,dp,connected comp etc)
->solve or leave it (- tutorial improves you in minimal way -)
*/
 
public static void main (String []args) {
precomp();

int times=ni();while(times-->0){solve();}out.close();}
 
static void solve(){
  int n=ni();
  Integer a[]=new Integer[n+1];a[0]=0;
  for(int i=1;i<=n;i++){a[i]=ni();}
   
  Arrays.sort(a);
  if(a[n]==a[n-1]){out.println(factorial[n]);}
  else if(a[n]>a[n-1]+1){out.println(0);}
  else{
    int cnt=0;int j=n-1;long ans=factorial[n];
    while(j>=1 && a[j]+1==a[n]){cnt++;j--;}
   
    int p=cnt+1;int curr=n - (cnt+1);
    long delta=0;
    while(p<=n){
       long cd= C(curr,n-p)*factorial[n-p];cd%=mod;
       cd=cd*factorial[p-1];cd%=mod;
       delta+=cd;delta%=mod;p++; 
    }
    ans=ans+mod-delta;ans%=mod;
    out.println(ans);
  }
  
  return;
}
 

//-----------------Utility--------------------------------------------
 
static int N=2000005;
static long inv[];
static long factorial[];
 
static void precomp(){
 inv=new long[N+1];factorial=new long[N+1];
 inv[0]=1;factorial[0]=1l;
 long j=1;
 for(int i=1;i<=N;i++){factorial[i]=(j*factorial[i-1])%mod;j++;}
 j=N-1;
 inv[N]=power(factorial[N],mod-2);
 for(int i=N-1;i>=0;i--){ inv[i]=((j+1)*inv[i+1])%mod;j--;}
 
}
 
static long C(int n,int r){
   if(r<0 || r>n)return 0l;
   long a=( ( ( factorial[n]*inv[r] )%mod )*inv[n-r])%mod;
   return a;
 }


static long gcd(long a,long b){if(b==0)return a; return gcd(b,a%b);}
 
static int Max=Integer.MAX_VALUE; static long mod=998244353;
 
//static int v(char c){return (int)(c-'a');}
 
public static long power(long x, long y )
    {
        //0^0 = 1
        long res = 1L;
        x = x%mod;
        while(y > 0)
        {
            if((y&1)==1)
                res = (res*x)%mod;
            y >>= 1;
            x = (x*x)%mod;
        }
        return res;
    }
 
/*static class Pair implements Comparable<Pair>{
        int id;int value;Pair next;
        public Pair(int id,int value) {
         
          this.id=id;this.value=value;next=null;
        }
        @Override
        public int compareTo(Pair p){return Long.compare(value,p.value);}
    }
*/ 
 
//----------------------I/O---------------------------------------------
 
static InputStream inputStream = System.in;
static OutputStream outputStream = System.out;
static FastReader in=new FastReader(inputStream);
static PrintWriter out=new PrintWriter(outputStream);
 
static class FastReader 
{ 
  BufferedReader br; 
  StringTokenizer st; 
 
        FastReader(InputStream is) {
            br = new BufferedReader(new InputStreamReader(is));
        }
 
  public String next() 
  { 
      while (st == null || !st.hasMoreElements()) 
      { 
          try
          { 
              st = new StringTokenizer(br.readLine()); 
          } 
          catch (IOException  e) 
          { 
              e.printStackTrace(); 
          } 
      } 
      return st.nextToken(); 
  } 
 
  public int nextInt() 
  { 
      return Integer.parseInt(next()); 
  } 
 
  public long nextLong() 
  { 
      return Long.parseLong(next()); 
  } 
 
 public  double nextDouble() 
  { 
      return Double.parseDouble(next()); 
  } 
 
 
  String nextLine() 
  { 
      String str = ""; 
      try
      { 
          str = br.readLine(); 
      } 
      catch (IOException e) 
      { 
          e.printStackTrace(); 
      } 
      return str; 
  } 
}
//Only for Integer Input
/*static int ni() {
        try {
            boolean in = false;
            int res = 0;
            for (;;) {
                int b = System.in.read() - '0';
                if (b >= 0) {
                    in = true;
                    res = 10 * res + b;
                }
                else if (in)
                    return res;
            }
        } catch (IOException e) {
            throw new Error(e);
        }
    }*/
static int ni(){return in.nextInt();}
static long nl(){return in.nextLong();}
static double nd(){return in.nextDouble();}
static String ns(){return in.nextLine();}
}