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.
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long  
#define ll long long
#define rep(i,n) for(int i=0;i<n;++i)
#define repa(i,a,n) for(int i=a;i<n;++i)
#define repr(i,n) for(int i=n-1;i>=0;--i)
#define pi pair<int ,int > 
#define pii pair<pi,int>
#define vi vector<int>
#define vvi vector<vi>
#define pb push_back 
#define fi first
#define sec second
#define all(v) v.begin(),v.end()
#define s(v) v.size()
#define Print(a) for(auto i:a) cout<<i<<" "; cout<<"\n";
#define Scan(a) rep(i,s(a)) cin>>a[i];
int mod = 998244353 ;
bool comp(vector<int> a, vector<int> b){
    if(a[1]<b[1])return true;
    return false;
}
ll fastexp(ll x,ll a){
    ll res = 1;
    while(a>0){
        if(a&1){
            res = (res*x)%mod;
        }
        a=a>>1;
        x=(x*x)%mod;
    }
    return res;
}
ll inverse(ll n){
    return fastexp(n,mod-2);
}
template <typename T>
void add(T &a, T b){
    a += b;
    if(a >= mod)a -= mod;
}
template <typename T>
void sub(T &a, T b){
    a -= b;
    if(a < 0)a += mod;
}
template <typename T>
void mul(T &a, T b){
    a *= b;
    if(a >= mod)a %= mod;
}
vi fact(2e5 + 5,1);
ll binPow(ll a,ll b)
{
    if (b == 0)return 1;
    if (b == 1)return a;
    ll ret = binPow(a,b/2);
    if (b%2 == 0)return (ret * ret)%mod;
    return ((ret * ret)%mod * a)%mod;
}
ll inv(ll a)
{
    return (binPow(a,mod - 2)%mod + mod)%mod;
}
ll ncr(ll a,ll b)
{
    if (b < 0 or a < 0)return 0;
    return (((fact[a] * inv(fact[b]))%mod * inv(fact[a - b]))%mod + mod)%mod;
}
void Fact(){
        for (int i = 1;i<=2e5;i++)fact[i] = (i * fact[i - 1])%mod;

}
void solve(){
        int n;
        cin>>n;
        vi a(n + 1);
        for (int i = 1;i<=n;i++)cin>>a[i];
        sort(a.begin() + 1,a.end());
        if (a[n] == a[n - 1]){
            cout<<fact[n]<<'\n';
            return;
        }   
        if (a[n] > a[n - 1] + 1){
            cout<<0<<'\n';
            return ;
        }
        ll cnt = 0;
        for (int i = 1;i<=n;i++){
            if (a[i] == a[n - 1])
                cnt++; 
        }

        int ans = fact[n];
        repa(i,1,n+1){
            if(i>cnt)
            ans = ans - ncr(i-1, cnt)*fact[n-1-cnt]*fact[cnt];
        }
        if(ans<0)ans += mod;
        cout<<ans;



    

}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    #ifndef ONLINE_JUDGE
    freopen("input1.txt", "return", stdin);
    freopen("output1.txt", "w", stdout);
    #endif
    Fact();
  //  cout<<ncr(4,4);
   // rep(i,10)cout<<fact[i]<<" ";
    int t=1;
    cin>>t;
    while(t--){
        solve();
        cout<<endl;
       // printf("\n");
    }
    return 0;
}       