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.
						/*
						ID: abdelra29
	LANG: JAVA
	PROG: zerosum
						*/
							/*
							TO LEARN
					
							2-euler tour
						
							*/
							/*
							TO SOLVE 
							*/
							/*
							bit manipulation shit
							1-Computer Systems: A Programmer's Perspective
							2-hacker's delight
							*/
							/*
							TO WATCH
							
							*/
							            import java.util.*;
									    import java.math.*;
									    import java.io.*; 
									    import java.util.stream.Collectors;


									       public class A{
							            static FastScanner scan=new FastScanner();
										     public static PrintWriter out = new PrintWriter (new BufferedOutputStream(System.out));
static  long[] fac;
static long power(long x, long y, long p)
    {
 
        // Initialize result
        long res = 1;
 
        // Update x if it is more than or
        // equal to p
        x = x % p;
 
        while (y > 0) {
 
            // If y is odd, multiply x
            // with result
            if (y % 2 == 1)
                res = (res * x) % p;
 
            // y must be even now
            y = y >> 1; // y = y/2
            x = (x * x) % p;
        }
 
        return res;
    }
 
    // Returns n^(-1) mod p
    static long modInverse(long n, long p)
    {
        return power(n, p - 2, p);
    }
 
    // Returns nCr % p using Fermat's
    // little theorem.
    static long nCrModPFermat(long n, long r,
                             long p)
    {
 
          if (n<r)
              return 0;
      // Base case
        if (r == 0)
            return 1;
 
        // Fill factorial array so that we
        // can find all factorial of r, n
        // and n-r
       
        fac[0] = 1;
 

 
        return (fac[(int)n] * modInverse(fac[(int)r], p)
                % p * modInverse(fac[(int)(n - r)], p)
                % p)
            % p;
    }
 
static int cntR=0;
static Set<Integer>dis=new HashSet<Integer>();
static void permute(java.util.List<Integer> arr, int k,int my[],int n){
        for(int i = k; i < arr.size(); i++){
            java.util.Collections.swap(arr, i, k);
            permute(arr, k+1,my,n);
            java.util.Collections.swap(arr, k, i);
        }
        if (k == arr.size() -1){
            int idx=0,last=-1;
            ArrayList<Integer>tmp=new ArrayList<Integer>(arr);
            while(true)
            {
            	if(idx==arr.size())
            	{
            		idx=0;
            	}
            	boolean is=false;
            	int cnt=0,o=0,id=0;
            	for(int i:tmp){
            		if(i>0){
            			if(arr.get(id)==4)
            				o=id;
            			cnt++;
            			
            			is=true;
            		}
id++;
            	}
            		if(cnt==1&&tmp.get(o)>1)
            		{

            			cntR++;
            			dis.add(o);
            			out.println(arr);
            			break;
            			//out.println(arr.get(o));
            			//out.println(arr);
            		}
            		else if(cnt==1&&o==5&&arr.get(o)==4)
            		{
            			//out.println(arr);
            			//out.println(tmp);
            		}
            		if(!is)
            			break;
            		if(tmp.get(idx)>=1)
            			tmp.set(idx,tmp.get(idx)-1);
            		idx++;
            }
        }
    }
    static long mod=(long)998244353L;
			public static void main(String[] args)  throws Exception 
							      {
							 /*
							 very important tips 
							 1-just fucking think backwards once in your shitty life
							 2-consider brute forcing and finding some patterns and observations
							 3-when you're in contest don't get out because you think there is no enough time
							 4-don't get stuck on one approach 
							 */
						   
				//scan=new FastScanner("helpcross.in");
			//	out = new PrintWriter("helpcross.out");

						
									 							 /*
									 READING 
							
									 3-Introduction to DP with Bitmasking codefoces
									 4-Bit Manipulation hackerearth
									 5-read more about mobious and inculsion-exclusion 
				 				 6-read more about Fermat little theorem
									 */
				 				 /*
				 				 when a permutation is bad that means there is gonna be sometime that i-th member has tasks more than 1 but the 
				 				 all the other members 
				 				 -we can get  permutations and delete bad 
				 				 -if the diff between the largest and second largest is bigger than 1 then the ans is 0
				 				 if there is more than 1 biggest then the ans is n!
				 				 -let's say x is the largest then for an array to bad there shouldn't be x-1 after it  
				 				 */
									         fac=new long [(int)2e5+4];
									        fac[1]=1;
									        for(long i=2;i<=2e5;i++)
									        	fac[(int)i]=(fac[(int)(i-1)]*i)%mod;
					
int tt=1;
									tt=scan.nextInt();
								int T=1;
								 outer:while(tt-->0)
								    {
								    	int n=scan.nextInt();
								    	ArrayList<Long>arr=new ArrayList<Long>();
								    	int max=0;
								    	Map<Long,Integer>map=new HashMap<Long,Integer>();
								    	for(int i=0;i<n;i++)
								    	{
								    		arr.add(scan.nextLong());
								    		map.put(arr.get(i),map.getOrDefault(arr.get(i),0)+1);								    		
								    	}
								    	Collections.sort(arr);
								    	if(arr.get(n-1)-arr.get(n-2)>=2)
								    	{
								    		out.println(0);
								    		continue outer;
								    	}
								    	if(map.get(arr.get(n-1))>1)
								    	{
								    		out.println(fac[n]);
								    		continue outer;
								    	}
								    	long have=map.get(arr.get(n-2));
								    long res=0;
								    	for(int i=n;i>=1;i--)
								    	{
								    		if(i==n)
								    		{
								    			res+=(fac[n-1]);
								    			res=res%mod;
								    			//out.println(res);
								    		}
								    		else {
								    			long cur=n-(have+1);
								    			if(n-i<=cur)
								    			{
								    				res+=((fac[i-1]*nCrModPFermat(cur,n-i,mod))%mod*fac[n-i]);
								    				res=res%mod;
								    			}
								    			else{ 
								    			//	out.println("I "+i);
								    				break;
								    		}
								    	}
								    	}
								    	out.println(((fac[n]-res)%mod+mod)%mod);

								    //	permute(arr,0,new int[1],n);
								    //	out.println(cntR);
//								out.println(dis);

								    
								  			   	
	 }							
	
        

			out.close();
						}
						
						

						static class special implements Comparable<special>{
						int cnt,idx;
						String s;
						public special(int cnt,int idx,String s)
						{
							this.cnt=cnt;
							this.idx=idx;
							this.s=s;
						}

							 @Override
									            public int hashCode() {
									                return (int)42;
									            }
							  @Override
									            public boolean equals(Object o){
									            //	System.out.println("FUCK");
									                if (o == this) return true;
									                if (o.getClass() != getClass()) return false;
									                special t = (special)o;
									                return t.cnt == cnt && t.idx == idx;
									            }
									            public int compareTo(special o1)
									            {
									            	if(o1.cnt==cnt)
									            	{
									            		return o1.idx-idx;
									            	}
									            	return o1.cnt-cnt;
									            }
						}
			
									   
									     static long binexp(long a,long n)
									    {
									        if(n==0)
									            return 1;
									        long res=binexp(a,n/2);
									        if(n%2==1)
									            return res*res*a;
									        else 
									            return res*res;
									    }
									     
									    static long powMod(long base, long exp, long mod) {
									           if (base == 0 || base == 1) return base;
									           if (exp == 0) return 1;
									           if (exp == 1) return (base % mod+mod)%mod;
									           long R = (powMod(base, exp/2, mod) % mod+mod)%mod;
									           R *= R;
									           R %= mod;
									           if ((exp & 1) == 1) {
									               return (base * R % mod+mod)%mod;
									           }
									           else return (R %mod+mod)%mod;
									       }
									    static double dis(double x1,double y1,double x2,double y2)
									    {
									        return Math.sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
									    }
									    static long mod(long x,long y)
									        {
									            if(x<0)
									                x=x+(-x/y+1)*y;
									            return x%y;
									        }
									     public static  long pow(long b, long e) {
									                long r = 1;
									                while (e > 0) {
									                    if (e % 2 == 1) r = r * b ;
									                    b = b * b;
									                    e >>= 1;
									                }
									                return r;
									            }
									    private static void sort(int[] arr) {
									            List<Integer> list = new ArrayList<>();
									            for (int object : arr) list.add(object);
									            Collections.sort(list);
									        //Collections.reverse(list);
									            for (int i = 0; i < list.size(); ++i) arr[i] = list.get(i);
									        }
									    private static void sort2(long[] arr) {
									            List<Long> list = new ArrayList<>();
									            for (Long object : arr) list.add(object);
									            Collections.sort(list);
									        Collections.reverse(list);
									            for (int i = 0; i < list.size(); ++i) arr[i] = list.get(i);
									        }
									     static class FastScanner
							{
							    private int BS = 1 << 16;
							    private char NC = (char) 0;
							    private byte[] buf = new byte[BS];
							    private int bId = 0, size = 0;
							    private char c = NC;
							    private double cnt = 1;
							    private BufferedInputStream in;
							 
							    public FastScanner() {
							        in = new BufferedInputStream(System.in, BS);
							    }
							 
							    public FastScanner(String s) {
							        try {
							            in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
							        } catch (Exception e) {
							            in = new BufferedInputStream(System.in, BS);
							        }
							    }
							 
							    private char getChar() {
							        while (bId == size) {
							            try {
							                size = in.read(buf);
							            } catch (Exception e) {
							                return NC;
							            }
							            if (size == -1) return NC;
							            bId = 0;
							        }
							        return (char) buf[bId++];
							    }
							 
							    public int nextInt() {
							        return (int) nextLong();
							    }
							 
							    public int[] nextInts(int N) {
							        int[] res = new int[N];
							        for (int i = 0; i < N; i++) {
							            res[i] = (int) nextLong();
							        }
							        return res;
							    }
							 
							    public long[] nextLongs(int N) {
							        long[] res = new long[N];
							        for (int i = 0; i < N; i++) {
							            res[i] = nextLong();
							        }
							        return res;
							    }
							 
							    public long nextLong() {
							        cnt = 1;
							        boolean neg = false;
							        if (c == NC) c = getChar();
							        for (; (c < '0' || c > '9'); c = getChar()) {
							            if (c == '-') neg = true;
							        }
							        long res = 0;
							        for (; c >= '0' && c <= '9'; c = getChar()) {
							            res = (res << 3) + (res << 1) + c - '0';
							            cnt *= 10;
							        }
							        return neg ? -res : res;
							    }
							 
							    public double nextDouble() {
							        double cur = nextLong();
							        return c != '.' ? cur : cur + nextLong() / cnt;
							    }
							 
							    public double[] nextDoubles(int N) {
							        double[] res = new double[N];
							        for (int i = 0; i < N; i++) {
							            res[i] = nextDouble();
							        }
							        return res;
							    }
							 
							    public String next() {
							        StringBuilder res = new StringBuilder();
							        while (c <= 32) c = getChar();
							        while (c > 32) {
							            res.append(c);
							            c = getChar();
							        }
							        return res.toString();
							    }
							 
							    public String nextLine() {
							        StringBuilder res = new StringBuilder();
							        while (c <= 32) c = getChar();
							        while (c != '\n') {
							            res.append(c);
							            c = getChar();
							        }
							        return res.toString();
							    }
							 
							    public boolean hasNext() {
							        if (c > 32) return true;
							        while (true) {
							            c = getChar();
							            if (c == NC) return false;
							            else if (c > 32) return true;
							        }
							    }
							}

									     static class Pair implements Comparable<Pair>{
									            public long x, y,z;
									            public Pair(long x1, long y1,long z1) {
									                x=x1;
									                y=y1;
									                z=z1;
									            }
									             public Pair(long x1, long y1) {
									                x=x1;
									                y=y1;
									    
									            }
									            
									            @Override
									            public int hashCode() {
									                return (int)(x + 31 * y);
									            }
									            public String toString() {
									                return x + " " + y+" "+z;
									            }
									            @Override
									            public boolean equals(Object o){
									                if (o == this) return true;
									                if (o.getClass() != getClass()) return false;
									                Pair t = (Pair)o;
									                return t.x == x && t.y == y&&t.z==z;
									            }
									    public int compareTo(Pair o)
									    {
									    								  	
									  if(x==o.x)
									  	return (int)(y-o.y);
									    	return (int)(x-o.x);
									     
									        }
									     
									    }
									}
									
									    
									   

									     
