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.
//package codechef;
import java.io.*;
import java.util.*;



public class cp_class {

	static int mod=998244353;
	
//	static  Reader sc=new Reader();
	   static FastReader sc=new FastReader(System.in);
	   
	   
	   	
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		//FastReader sc=new FastReader();
			
			
			
		int t=sc.nextInt();
		factorial(mod);
		InverseofNumber(mod);
		InverseofFactorial(mod);
		while(t-->0)
		{
			
			int n=sc.nextInt();
			int[] arr=new int[n];
			int max=int_min;
			for (int i = 0; i < arr.length; i++) {
				arr[i]=sc.nextInt();
				max=Math.max(max, arr[i]);
			}
			
			int freqMax=0,freqnext=0;
			for(int i=0;i<n;i++)
			{
				if(arr[i]==max)
					freqMax++;
				if(arr[i]==max-1)
					freqnext++;
			}
			
			if(freqMax>1)
			{
				out.println(fact[n]%mod);
			}
			else if(freqnext<1)
			{
				out.println("0");
			}
			else {
				//out.println(fact[freqnext]+" "+fact[n-freqnext-1]);
				long cnt=(fact[freqnext]*fact[n-freqnext-1])%mod;
				//out.println(cnt);
				for(int pos=freqnext+2;pos<=n;pos++)
				{
					long temp=fact[pos-1]%mod;
					temp=(temp*Binomial(n-freqnext-1, pos-freqnext-1, mod))%mod;
					temp=(temp*fact[n-pos])%mod;
					cnt=(cnt+temp)%mod;
				}
				
				out.println((fact[n]-cnt+mod)%mod);
			}
			
			
		}
			
			out.flush();
			out.close();
			System.gc();
	
	}
	
	
	


	/*
	   ...SOLUTION ENDS HERE...........SOLUTION ENDS HERE...
	 */
	 
	static boolean prime[];
	
	static void swap(int arr[],int i,int j)
	{
		int temp=arr[i];
		arr[i]=arr[j];
		arr[j]=temp;
	}
	
	static void sieveOfEratosthenes(int n)
    {
        // Create a boolean array
        // "prime[0..n]" and
        // initialize all entries
        // it as true. A value in
        // prime[i] will finally be
        // false if i is Not a
        // prime, else true.
        prime= new boolean[n + 1];
        for (int i = 0; i <= n; i++)
            prime[i] = true;
 
        for (int p = 2; p * p <= n; p++)
        {
            // If prime[p] is not changed, then it is a
            // prime
            if (prime[p] == true)
            {
                // Update all multiples of p
                for (int i = p * p; i <= n; i += p)
                    prime[i] = false;
            }
        }
 
        // Print all prime numbers
//        for (int i = 2; i <= n; i++)
//        {
//            if (prime[i] == true)
//                System.out.print(i + " ");
//        }
    }
	
	
	
	
	
	
	
	
	
	
	
	
	static int N = (int)2e5+5; 
	 
	// Array to store inverse of 1 to N
	static long[] factorialNumInverse = new long[N + 1];
	 
	// Array to precompute inverse of 1! to N!
	static long[] naturalNumInverse = new long[N + 1];
	 
	// Array to store factorial of first N numbers
	static long[] fact = new long[N + 1];
	 
	// Function to precompute inverse of numbers
	public static void InverseofNumber(int p)
	{
	    naturalNumInverse[0] = naturalNumInverse[1] = 1;
	     
	    for(int i = 2; i <= N; i++)
	        naturalNumInverse[i] = naturalNumInverse[p % i] *
	                                 (long)(p - p / i) % p;
	}
	 
	// Function to precompute inverse of factorials
	public static void InverseofFactorial(int p)
	{
	    factorialNumInverse[0] = factorialNumInverse[1] = 1;
	 
	    // Precompute inverse of natural numbers
	    for(int i = 2; i <= N; i++)
	        factorialNumInverse[i] = (naturalNumInverse[i] *
	                           factorialNumInverse[i - 1]) % p;
	}
	 
	// Function to calculate factorial of 1 to N
	public static void factorial(int p)
	{
	    fact[0] = 1;
	 
	    // Precompute factorials
	    for(int i = 1; i <= N; i++)
	    {
	        fact[i] = (fact[i - 1] * (long)i) % p;
	    }
	}
	 
	// Function to return nCr % p in O(1) time
	public static long Binomial(int N, int R, int p)
	{
	     
	    // n C r = n!*inverse(r!)*inverse((n-r)!)
	    long ans = ((fact[N] * factorialNumInverse[R]) %
	                       p * factorialNumInverse[N - R]) % p;
	     
	    return ans;
	}
	
	static boolean util(int a,int b,int c)
	{
		if(b>a)util(b, a, c);
		
		while(c>=a)
		{
			c-=a;
			if(c%b==0)
				return true;
		}
		
		
		return (c%b==0);
	}
	
	static boolean check(int arr[])
	{
		for (int i = 1; i < arr.length; i++) {
		if(arr[i-1]>arr[i])
			return false;
		}
		return true;
	}
	
	static void flag(boolean flag)
	   {
	       out.println(flag ? "YES" : "NO");
	       out.flush();
	   }
	   
	static ArrayList<Long> luckNums;
	static void luckyNum(long x,long p10)
	{
		luckNums.add(x);
		if(x>(long)1e10)
			return;
		luckyNum(x+4*p10, p10*10);
		luckyNum(x+7*p10, p10*10);
		
	}
	
	 /*                     
	    Map<Long,Long> map=new HashMap<>();
	             for(int i=0;i<n;i++)
	               {
	                  if(!map.containsKey(a[i]))
	                   map.put(a[i],1);
	                 else
	                   map.replace(a[i],map.get(a[i])+1);
	               }
	     
	    Set<Map.Entry<Long,Long>> hmap=map.entrySet();
	             for(Map.Entry<Long,Long> data : hmap)
	               {
	          
	               }
	       
	   Iterator<Integer> it = set.iterator();
	          while(it.hasNext()) 
	           { 
	            int x=it.next();
	           }
	   */

	
	
	static void print(int a[])
	  {
	     int n=a.length;
	     for(int i=0;i<n;i++)
	       {
	          out.print(a[i]+" ");
	       }
	     out.println();
	     out.flush();
	  }
	static void print(long a[])
	  {
	     int n=a.length;
	     for(int i=0;i<n;i++)
	       {
	          out.print(a[i]+" ");
	       }
	     out.println();
	     out.flush();
	  } 
	static void print_int(ArrayList<Integer> al)
	  {
	     int si=al.size();
	     for(int i=0;i<si;i++)
	       {
	          out.print(al.get(i)+" ");
	       }
	     out.println();
	     out.flush();
	  }
	static void print_long(ArrayList<Long> al)
	  {
	     int si=al.size();
	     for(int i=0;i<si;i++)
	       {
	          out.print(al.get(i)+" ");
	       }
	     out.println();
	     out.flush();
	  }
	  
	static int LowerBound(int a[], int x) 
	 { // x is the target value or key
	  int l=-1,r=a.length;
	  while(l+1<r) {
	    int m=(l+r)>>>1;
	    if(a[m]>=x) r=m;
	    else l=m;
	  }
	  return r;
	}
	
	
	static int lowerIndex(int arr[], int n, int x)
    {
        int l = 0, h = n - 1;
        while (l <= h)
        {
            int mid = (l + h) / 2;
            if (arr[mid] >= x)
                h = mid - 1;
            else
                l = mid + 1;
        }
        return l;
    }
     
	
	 static int UpperBound(int a[], int x)
	  {// x is the key or target value
	    int l=-1,r=a.length;
	    while(l+1<r) {
	       int m=(l+r)>>>1;
	       if(a[m]<=x) l=m;
	       else r=m;
	    }
	    return l+1;
	 }
	 static class DisjointUnionSets
	 {
	    int[] rank, parent;
	    int n;
	    // Constructor
	    public DisjointUnionSets(int n)
	    {
	        rank = new int[n];
	        parent = new int[n];
	        this.n = n;
	        makeSet();
	    }
	    // Creates n sets with single item in each
	    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];
	    }
	    // Unites the set that includes x and the set
	    // that includes 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 // if ranks are the same
	        {
	         parent[yRoot] = xRoot;
	            rank[xRoot] = rank[xRoot] + 1;
	        }
	    }
	 }

	 
//	static class countClass{
//		int cnt;
//		public countClass() {
//			this.cnt=0;
//			// TODO Auto-generated constructor stub
//		}
//	}

	 
	 
	static class Graph
	  {
	        int v;
	        ArrayList<Integer> list[];
	        Graph(int v)
	        {
	            this.v=v;
	            list=new ArrayList[v+1];
	            for(int i=1;i<=v;i++)
	                list[i]=new ArrayList<Integer>();
	        }
	        void addEdge(int a, int b)
	        {
	            this.list[a].add(b);
	        }
	    }
	
//	static class GraphMap{
//		Map<String,ArrayList<String>> graph;
//		GraphMap() {
//			// TODO Auto-generated constructor stub
//			graph=new HashMap<String,ArrayList<String>>();
//			
//		}
//		void addEdge(String a,String b)
//		{
//			if(graph.containsKey(a))
//			this.graph.get(a).add(b);
//			else {
//				this.graph.put(a, new ArrayList<>());
//				this.graph.get(a).add(b);
//			}
//		}
//	}
//	static void dfsMap(GraphMap g,HashSet<String> vis,String src,int ok)
//	{
//		vis.add(src);
//		
//		if(g.graph.get(src)!=null)
//		{
//			for(String each:g.graph.get(src))
//			{
//				if(!vis.contains(each))
//				{
//					dfsMap(g, vis, each, ok+1);
//				}
//			}
//		}
//		
//		cnt=Math.max(cnt, ok);
//	}
	static double sum[];
	static double cnt;
	static void DFS(Graph g, boolean[] visited, int u,double path)
		{
	        visited[u]=true;
	        sum[u]=0;
	        int k=0;
	        for(int i=0;i<g.list[u].size();i++)
	        {
	            int v=g.list[u].get(i);
	            
	            if(!visited[v])
	            {
	            	DFS(g, visited, v,path+1);
	            	sum[u]+=sum[v];
	            	k++;
	            }
	            
	        }
	        if(k!=0)
	        sum[u]=sum[u]/(double)k +1;

	  } 
	
	
	  
	 static class Pair implements Comparable<Pair>
	    {
//	       int x,y;
	       long first,second;
//	       Pair(int x,int y)
//	        {
//	           this.x=x;
//	           this.y=y;
//	        }
	       public Pair(long x,long y) {
			// TODO Auto-generated constructor stub
	    	   this.first=x;
	    	   this.second=y;
		}
		@Override
		public int compareTo(Pair o) {
			// TODO Auto-generated method stub
			if(this.first>o.first)
				return 1;
			else if (this.first<o.first) {
				return -1;
			} else{
				return 0;
			}
			
		}
	    }
	   
	static long sum_array(int a[])
	 {
	    int n=a.length;
	    long sum=0;
	    for(int i=0;i<n;i++)
	     sum+=a[i];
	    return sum;
	 }
	static long sum_array(long a[])
	 {
	    int n=a.length;
	    long sum=0;
	    for(int i=0;i<n;i++)
	     sum+=a[i];
	    return sum;
	 }

	 static void sort(int[] a) 
	   {
			ArrayList<Integer> l=new ArrayList<>();
			for (int i:a) l.add(i);
			Collections.sort(l);
			for (int i=0; i<a.length; i++) a[i]=l.get(i);
		}
	static void sort(long[] a) 
	   {
			ArrayList<Long> l=new ArrayList<>();
			for (long i:a) l.add(i);
			Collections.sort(l);
			for (int i=0; i<a.length; i++) a[i]=l.get(i);
		}

	static void reverse_array(int a[])
	 {
	    int n=a.length;
	    int i,t; 
	    for (i = 0; i < n / 2; i++) { 
	            t = a[i]; 
	            a[i] = a[n - i - 1]; 
	            a[n - i - 1] = t; 
	        } 
	 }
	static void reverse_array(long a[])
	 {
	    int n=a.length;
	    int i; long t; 
	    for (i = 0; i < n / 2; i++) { 
	            t = a[i]; 
	            a[i] = a[n - i - 1]; 
	            a[n - i - 1] = t; 
	        } 
	 }
	 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 long gcd(long a, long b) 
	    { 
	        if (a == 0) 
	            return b; 
	          
	        return gcd(b%a, a); 
	    } 
	static int gcd(int a, int b) 
	    { 
	        if (a == 0) 
	            return b; 
	          
	        return gcd(b%a, a); 
	    } 

	   static class FastReader{
	 
	        byte[] buf = new byte[2048];
	        int index, total;
	        InputStream in;
	 
	        FastReader(InputStream is) {
	            in = is;
	        }
	 
	        int scan() throws IOException {
	            if (index >= total) {
	                index = 0;
	                total = in.read(buf);
	                if (total <= 0) {
	                    return -1;
	                }
	            }
	            return buf[index++];
	        }
	 
	        String next() throws IOException {
	            int c;
	            for (c = scan(); c <= 32; c = scan());
	            StringBuilder sb = new StringBuilder();
	            for (; c > 32; c = scan()) {
	                sb.append((char) c);
	            }
	            return sb.toString();
	        }
	 
	        int nextInt() throws IOException {
	            int c, val = 0;
	            for (c = scan(); c <= 32; c = scan());
	            boolean neg = c == '-';
	            if (c == '-' || c == '+') {
	                c = scan();
	            }
	            for (; c >= '0' && c <= '9'; c = scan()) {
	                val = (val << 3) + (val << 1) + (c & 15);
	            }
	            return neg ? -val : val;
	        }
	 
	        long nextLong() throws IOException {
	            int c;
	            long val = 0;
	            for (c = scan(); c <= 32; c = scan());
	            boolean neg = c == '-';
	            if (c == '-' || c == '+') {
	                c = scan();
	            }
	            for (; c >= '0' && c <= '9'; c = scan()) {
	                val = (val << 3) + (val << 1) + (c & 15);
	            }
	            return neg ? -val : val;
	        }
	    }
	   
	    static class Reader 
	    { 
	        final private int BUFFER_SIZE = 1 << 16; 
	        private DataInputStream din; 
	        private byte[] buffer; 
	        private int bufferPointer, bytesRead; 
	  
	        public Reader() 
	        { 
	            din = new DataInputStream(System.in); 
	            buffer = new byte[BUFFER_SIZE]; 
	            bufferPointer = bytesRead = 0; 
	        } 
	  
	        public Reader(String file_name) throws IOException 
	        { 
	            din = new DataInputStream(new FileInputStream(file_name)); 
	            buffer = new byte[BUFFER_SIZE]; 
	            bufferPointer = bytesRead = 0; 
	        } 
	  
	        public String readLine() throws IOException 
	        { 
	            byte[] buf = new byte[64]; // line length 
	            int cnt = 0, c; 
	            while ((c = read()) != -1) 
	            { 
	                if (c == '\n') 
	                    break; 
	                buf[cnt++] = (byte) c; 
	            } 
	            return new String(buf, 0, cnt); 
	        } 
	  
	        public int nextInt() throws IOException 
	        { 
	            int ret = 0; 
	            byte c = read(); 
	            while (c <= ' ') 
	                c = read(); 
	            boolean neg = (c == '-'); 
	            if (neg) 
	                c = read(); 
	            do
	            { 
	                ret = ret * 10 + c - '0'; 
	            }  while ((c = read()) >= '0' && c <= '9'); 
	  
	            if (neg) 
	                return -ret; 
	            return ret; 
	        } 
	  
	        public long nextLong() throws IOException 
	        { 
	            long ret = 0; 
	            byte c = read(); 
	            while (c <= ' ') 
	                c = read(); 
	            boolean neg = (c == '-'); 
	            if (neg) 
	                c = read(); 
	            do { 
	                ret = ret * 10 + c - '0'; 
	            } 
	            while ((c = read()) >= '0' && c <= '9'); 
	            if (neg) 
	                return -ret; 
	            return ret; 
	        } 
	  
	        public double nextDouble() throws IOException 
	        { 
	            double ret = 0, div = 1; 
	            byte c = read(); 
	            while (c <= ' ') 
	                c = read(); 
	            boolean neg = (c == '-'); 
	            if (neg) 
	                c = read(); 
	  
	            do { 
	                ret = ret * 10 + c - '0'; 
	            } 
	            while ((c = read()) >= '0' && c <= '9'); 
	  
	            if (c == '.') 
	            { 
	                while ((c = read()) >= '0' && c <= '9') 
	                { 
	                    ret += (c - '0') / (div *= 10); 
	                } 
	            } 
	  
	            if (neg) 
	                return -ret; 
	            return ret; 
	        } 
	  
	        private void fillBuffer() throws IOException 
	        { 
	            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE); 
	            if (bytesRead == -1) 
	                buffer[0] = -1; 
	        } 
	  
	        private byte read() throws IOException 
	        { 
	            if (bufferPointer == bytesRead) 
	                fillBuffer(); 
	            return buffer[bufferPointer++]; 
	        } 
	  
	        public void close() throws IOException 
	        { 
	            if (din == null) 
	                return; 
	            din.close(); 
	        } 
	    }
	  static  PrintWriter out=new PrintWriter(System.out);
	  static int int_max=Integer.MAX_VALUE;
	  static int int_min=Integer.MIN_VALUE;
	  static long long_max=Long.MAX_VALUE;
	  static long long_min=Long.MIN_VALUE;

}


