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

public class A {

	static Scanner sc = new Scanner(System.in);
	// static Reader sc = new Reader();
	static StringBuilder out = new StringBuilder();

	static String testCase = "Case #";
	static long mod=998244353;
	static long fac[]=new long[3*(int)1e5];
	

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub

		int t = sc.nextInt();

		int tc = 0;

		fac[0]=1;
		
		for(int i=1;i<fac.length;i++) {
			
			fac[i]=fac[i-1]*i;
			fac[i]%=mod;
		}
		
		while (tc++ < t) {
		//	out.append(testCase + tc + ": ");
			A run = new A();

			run.run();
		}

		System.out.println(out);

	}

	static int a[][];

	static ArrayList<Long> al = new ArrayList<>();

	static class pair implements Comparable<pair> {

		int f, s;

		pair(int f, int s) {
			this.f = f;
			this.s = s;

		}

		@Override
		public int compareTo(pair o) {
			// TODO Auto-generated method stub

			return o.s - this.s;

		}

	}

	public void run() throws IOException {
		
		
		
		int n=sc.nextInt();
		int ar[]=new int[n];
		
		TreeMap<Integer,Integer> tm=new TreeMap<>();
		
		
		for(int i=0;i<n;i++) {
			
			ar[i]=sc.nextInt();
		
			tm.put(ar[i], tm.getOrDefault(ar[i], 0)+1);
		}
		
		long ans=fac[n];
		int key=tm.lastKey();
		
		int x=tm.get(key);
		
		tm.remove(key);
		
		if(x>1) {
			
			out.append(ans+"\n");return;
		}
	
		int key1=tm.lastKey();
		
		if(key1+1!=key) {
			
			out.append(0+"\n");return;
		}
		
		int  y=tm.get(key1);
		
		int z=n-(x+y);
		
		for(int i=0;i<=z;i++) {
			
			long deno=(fac[z-i])%mod;
			
			long val=(fac[z]*modInverse(deno,mod))%mod*(fac[y+z-i]);
			val%=mod;
			
			ans-=val;
			if(ans<0)ans+=mod;
			
			
			
		}
		
		out.append(ans+"\n");
		
		
		
		
		

	}
	
	
	
	
	static long modInverse(long a, long m)
    {
        long m0 = m;
        long y = 0, x = 1;
 
        if (m == 1)
            return 0;
 
        while (a > 1) {
            // q is quotient
            long q = a / m;
 
            long t = m;
 
            
            m = a % m;
            a = t;
            t = y;
 
            // Update x and y
            y = x - q * y;
            x = t;
        }
 
        // Make x positive
        if (x < 0)
            x += m0;
 
        return x;
    }

	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') {
					if (cnt != 0) {
						break;
					} else {
						continue;
					}
				}
				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();
		}
	}

}
