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.
/*
    Author : Akshat Jindal
    from NIT Jalandhar , Punjab , India
    JAI MATA DI
 */
import java.util.*;


import java.io.*;
import java.math.*;
import java.sql.Array;



public class Main {
	  static class FR{
		  
			BufferedReader br;
			StringTokenizer st;
			public FR() {
				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 mod = (long)(1e9 + 7);
	 
	static void sort(long[] arr ) {
		 ArrayList<Long> al = new ArrayList<>();
		 for(long e:arr) al.add(e);
		 Collections.sort(al);
		 for(int i = 0 ; i<al.size(); i++) arr[i] = al.get(i);
	 }
	static void sort(int[] arr ) {
		 ArrayList<Integer> al = new ArrayList<>();
		 for(int e:arr) al.add(e);
		 Collections.sort(al);
		 for(int i = 0 ; i<al.size(); i++) arr[i] = al.get(i);
	 }
	static int UB(long[] arr , long find , int l , int r) {
		while(l<=r) {
			int m = (l+r)/2;
			if(arr[m]<find) l = m+1;
			else r = m-1;
		}
		return l;
	}
	static int LB(long[] arr , long find,int l ,int r ) {
		while(l<=r) {
			int m = (l+r)/2;
			if(arr[m] > find) r = m-1;
			else l = m+1;
		}
		return r;
	}
	static int UB(int[] arr , long find , int l , int r) {
		while(l<=r) {
			int m = (l+r)/2;
			if(arr[m]<find) l = m+1;
			else r = m-1;
		}
		return l;
	}
	static int LB(int[] arr , long find,int l ,int r ) {
		while(l<=r) {
			int m = (l+r)/2;
			if(arr[m] > find) r = m-1;
			else l = m+1;
		}
		return r;
	}
	 static long gcd(long a, long b)
	  {      
	     if (b == 0)
	        return a;
	     return gcd(b, a % b); 
	  }
	 static boolean[] prime(int num) {
			boolean[] bool = new boolean[num];
		     
		      for (int i = 0; i< bool.length; i++) {
		         bool[i] = true;
		      }
		      for (int i = 2; i< Math.sqrt(num); i++) {
		         if(bool[i] == true) {
		            for(int j = (i*i); j<num; j = j+i) {
		               bool[j] = false;
		            }
		         }
		      }
		      if(num >= 0) {
		    	  bool[0] = false;
		    	  bool[1] = false;
		      }
		      
		      return bool;
		}
	 static void sort(char[] arr) {
		 ArrayList<Character> al = new ArrayList<Character>();
		 for(char cc:arr) al.add(cc);
		 Collections.sort(al);
		 for(int i = 0 ;i<arr.length ;i++) arr[i] = al.get(i);
		 
	 }
	 static long[][] ncr(int n, int k)
	    {
	        long C[][] = new long[n + 1][k + 1];
	        int i, j;
	 
	        // Calculate  value of Binomial
	        // Coefficient in bottom up manner
	        for (i = 0; i <= n; i++) {
	            for (j = 0; j <= Math.min(i, k); j++) {
	                // Base Cases
	                if (j == 0 || j == i)
	                    C[i][j] = 1;
	 
	                // Calculate value using
	                // previously stored values
	                else
	                    C[i][j] = (C[i - 1][j - 1] + C[i - 1][j])%mod;
	            }
	        }
	 
	        return C;
	    }
	 static long modInverse(long a, long m)
	    {
	        long g = gcd(a, m);
	       
	          return   power(a, m - 2, m);
	        
	    }
	   
	      static long power(long x, long y, long m)
	    {
	        if (y == 0)
	            return 1;
	        long p = power(x, y / 2, m) % m;
	        p = (int)((p * (long)p) % m);
	        if (y % 2 == 0)
	            return p;
	        else
	            return (int)((x * (long)p) % m);
	    }
	      static class DisjointUnionSets {
			    int[] rank, parent;
			    int n;
			  
			    public DisjointUnionSets(int n)
			    {
			        rank = new int[n];
			        parent = new int[n];
			        this.n = n;
			        makeSet();
			    }
			  
			    void makeSet()
			    {
			        for (int i = 0; i < n; i++) {
			          
			            parent[i] = i;
			        }
			    }
			  
			    int find(int x)
			    {
			        if (parent[x] != x) {
			        
			            parent[x] = find(parent[x]);
			  
			        }
			  
			        return parent[x];
			    }
			  
			    void union(int x, int y)
			    {
			        int xRoot = find(x), yRoot = find(y);
			  
			        if (xRoot == yRoot)
			            return;
			  
			        if (rank[xRoot] < rank[yRoot])
			  
			            parent[xRoot] = yRoot;
			  
			        else if (rank[yRoot] < rank[xRoot])
			  
			            parent[yRoot] = xRoot;
			  
			        else
			        {
			            parent[yRoot] = xRoot;
			  
			            rank[xRoot] = rank[xRoot] + 1;
			        }
			    }
			}
	      
/************************************************ Query **************************************************************************************/	  
	      static class SparseTable{
	    		
	    		private long[][] st;
	    		
	    		SparseTable(long[] arr){
	    			int n = arr.length;
	    			st = new long[n][25];
	    			log = new int[n+2];
	    			build_log(n+1);
	    			build(arr);
	    		}
	    		
	    		private void build(long[] arr) {
	    			int n = arr.length;
	    			
	    			for(int i = n-1 ; i>=0 ; i--) {
	    				for(int j = 0 ; j<25 ; j++) {
	    					int r = i + (1<<j)-1;
	    					if(r>=n) break;
	    					if(j == 0 ) st[i][j] = arr[i];
	    					else st[i][j] = Math.min(st[i][j-1] , st[ i + ( 1 << (j-1) ) ][ j-1 ] );
	    				}
	    			}
	    		}
	    		public long gcd(long a  ,long b) {
	    			if(a == 0) return b;
	    			return gcd(b%a , a);
	    		}
	    		public long query(int l ,int r) {
	    			int w = r-l+1;
	    			int power = log[w];
	    			return Math.min(st[l][power],st[r - (1<<power) + 1][power]);
	    		}
	    		private int[] log;
	    		void build_log(int n) {
	    			log[1] = 0;
	    			for(int i = 2 ; i<=n ; i++) {
	    				log[i] = 1 + log[i/2];
	    			}
	    		}
	    	}
//	  	static int query(int[] tree , int ss ,int se ,int qs , int qe,int index) {
//			
//			if(ss>=qs && se<=qe) return tree[index];
//			
//			if(qe<ss || se<qs) return Integer.MAX_VALUE;
//			
//			int mid = (ss + se)/2;
//			int left = query(tree , ss , mid , qs ,qe , 2*index);
//			int right= query(tree ,mid + 1 , se , qs ,qe , 2*index+1);
//			return Math.min(left, right);
//		}
//		static void buildTree(int[] a ,int s ,int e ,int[] tree ,int index ) {
//			if(s == e) {
//				tree[index] = a[s];
//				return;
//			}
//		
//			int mid = (s+e)/2;
//			
//			buildTree(a, s,  mid, tree, 2*index);
//			buildTree(a, mid+1, e, tree, 2*index+1);
//			
//			tree[index] = tree[2*index] + tree[2*index+1];
//		}
	  
/* ***************************************************************************************************************************************************/	 
	 
	      static FR sc = new FR();
	 static StringBuilder sb = new StringBuilder();
	 public static void main(String args[]) throws IOException {
	
		 int tc = 1;
		  tc = sc.nextInt();
		 mod = (long)(1e9 + 7);
		 while(tc-->0) {
			 TEST_CASE();
			 
		 }
		 System.out.println(sb);
	 }
	 
	 static void TEST_CASE() {
		 int n = sc.nextInt();
		 long[] arr = new long[n];
		 for(int i = 0 ; i<n ; i++) {
			 arr[i] = sc.nextLong();
		 }
		 sort(arr);
		 if(arr[n-1] - arr[n-2]>1) {
			 sb.append("0\n");
			 return;
		 }
		 mod = 998244353 ;
		  fac = new long[n+1];
		 fac[0] = 1;
		 for(int i = 1 ; i<=n ; i++) fac[i] = (fac[i-1]*i)%mod;
		 if(arr[n-1] == arr[n-2]) {
			 int c = 0;
			 int i = n-1;
			 while(i>=0 && arr[i] == arr[n-1]) {
				 i--;
				 c++;
			 }
			 long ans = 0;
			 long nc2 = (fac[c]*(modInverse(fac[2], mod)%mod * modInverse(fac[c-2], mod)%mod)%mod)%mod;
			 
//			 System.out.println(nc2);
			 for( i = 0 ; i<=n-2 ; i++) {
				ans = (ans + (((nc2*(fac[i])) %mod)*(fac[n-2-i])%mod) )%mod; 
			 }
			 sb.append(ans+"\n");
		 }else {
			 long c = 0;
			 int i = n-2;
			 while(i>=0 && arr[i] == arr[n-2]) {
				 i--;
				 c++;
			 }
			 long non = n - 1 - c;
			 long ans = fac[n] ;
			 for( i =1 ; i<=n ; i++) { 
				 long val = ncr(non , n-i);
				 val = (val* fac[n-i])%mod;
				 val = ( val * fac[i-1]);
				 ans = ((ans - val )%mod + mod)%mod;
			 }
			 sb.append((ans)+"\n");
		 }
		 
	 }
	 static long fac[];
	 static long ncr(long n ,long r) {
		 if(r>n || r<0) return 0;
		 long a = (modInverse(fac[(int)r], mod) * modInverse(fac[(int)(n-r)], mod));
		 
		 return (fac[(int)n]*a)%mod;
	 }
}



/*******************************************************************************************************************************************************/

/***

6
3 4 2 1 3 3

1 2 3 3 3 4

*/


