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.*;

/**
 * A simple template for competitive programming problems.
 */
public class Solution {
    //InputReader in = new InputReader("input.txt");
    final InputReader in = new InputReader(System.in);

    final PrintWriter out = new PrintWriter(System.out);
    final int mod = 998244353;
    void solve() {
        int t = in.nextInt();
        long[] fact = new long[2000034]; fact[0] = 1;
        for(int i=1; i<fact.length; i++) {
            fact[i] = (fact[i-1] * i)%mod;
        }
        while(t-->0) {
            int n = in.nextInt();
            int[] arr = in.nextArray(n);
            shuffle(arr);
            int max = 0;
            int maxCount = 0;
            for(int i=0; i<n; i++) {
                if(arr[i]>max) {
                    maxCount = 1;
                    max = arr[i];
                } else if(arr[i]==max) {
                    maxCount++;
                }
            }
            if(maxCount>1 || n==1) {
                out.println(fact[n]);
                continue;
            }
            int sCount = 0;
            for(int i=0; i<n; i++) {
                if(arr[i]==max-1) {
                    sCount++;
                }
            }
            if(sCount==0) {
                out.println(0);
                continue;
            }
            long ans = (fact[n] - ((fact[n]*modInverse(sCount+1, mod))%mod))%mod;
            out.println(ans<0 ? ans+mod : ans);
        }
    }
    public static long modInverse(long a, long m) {
        long mod = m;
        long x = 0, y = 1, lastx = 1, lasty = 0, temp;
        while (m != 0) {
            long q = a / m;
            long r = a % m;

            a = m;
            m = r;

            temp = x;
            x = lastx - q*x;
            lastx = temp;

            temp = y;
            y = lasty - q*y;
            lasty = temp;
        }
        return (lastx % mod + mod) % mod;
    }

	public class LST {

    /* *********************************** */
    /* CHANGE HERE FOR OTHER FUNCTIONALITY */

        private class Node {
            long ans;
            int fl;
            int ll;
            int length;
            int f;
            int l;

            void setLeaf(int i, int val) {
                ans = 1;
                fl = 1;
                ll = 1;
                f = val;
                l = val;
                length = 1;
            }

            void merge(LST.Node a, LST.Node b) {
                f = a.f;
                l = b.l;
                ans = a.ans + b.ans;
                if (a.l <= b.f) {
                    ans += (long) a.ll * b.fl;
                }
                fl = a.fl;
                ll = b.ll;
                if (a.fl == a.length && a.l <= b.f) {
                    fl += b.fl;
                }
                if (b.ll == b.length && a.l <= b.f) {
                    ll += a.ll;
                }
                length = a.length + b.length;
            }

            void split(LST.Node left, LST.Node right) {
            }

            void updateSingle(int val) {
                ans = 1;
                fl = 1;
                ll = 1;
                f = val;
                l = val;
                length = 1;
            }
        }
    /* CHANGE HERE FOR OTHER FUNCTIONALITY */
    /* *********************************** */

    private final int n;
    private final Node[] tree;
    private int ql, qr, val;

    public LST(int[] arr) {
        n = arr.length;
        int h = 32 - Integer.numberOfLeadingZeros(n-1) + 1;
        tree = new Node[1<<h];
        build(1, 0, arr.length-1, arr);
    }

    private void build(int i, int l, int r, int[] arr) {
        if (l == r) {
            tree[i] = new Node();
            tree[i].setLeaf(l, arr[l]);
        } else {
            int m = (l+r+1) / 2;
            build(2*i, l, m-1, arr);
            build(2*i+1, m, r, arr);
            tree[i] = new Node();
            tree[i].merge(tree[2*i], tree[2*i+1]);
        }
    }

    public void update(int ql, int qr, int val) {
        this.ql = ql;
        this.qr = qr;
        this.val = val;
        updateHelper(1, 0, n-1);
    }

    private void updateHelper(int i, int l, int r) {
        if (qr < l || ql > r) return;
        if (qr >= r && ql <= l) tree[i].updateSingle(val);
        else {
            tree[i].split(tree[2*i], tree[2*i+1]);
            int m = (l+r+1) / 2;
            updateHelper(2*i, l, m-1);
            updateHelper(2*i+1, m, r);
            tree[i].merge(tree[2*i], tree[2*i+1]);
        }
    }

    public Node query(int ql, int qr) {
        this.ql = ql;
        this.qr = qr;
        return queryHelper(1, 0, n-1);
    }

    private Node queryHelper(int i, int l, int r) {
        if (qr < l || ql > r) return null;
        if (qr >= r && ql <= l) return tree[i];
        tree[i].split(tree[2*i], tree[2*i+1]);
        int m = (l+r+1) / 2;

        Node ansLeft = queryHelper(2*i, l, m-1);
        Node ansRight = queryHelper(2*i + 1, m, r);
        if (ansLeft == null) return ansRight;
        if (ansRight == null) return ansLeft;
        Node answer = new Node();
        answer.merge(ansLeft, ansRight);
        return answer;
    }
}

    private void shuffle(int[] a) {
        int n = a.length;
        Random random = new Random();
        random.nextInt();
        for (int i = 0; i < n; i++) {
            int change = i + random.nextInt(n - i);
            swap(a, i, change);
        }
    }

    private static void swap(int[] a, int i, int j) {
        int helper = a[i];
        a[i] = a[j];
        a[j] = helper;
    }

    public static void main(final String[] args) throws FileNotFoundException {
        final Solution s = new Solution();
        final Long t1 = System.currentTimeMillis();
        s.solve();
        System.err.println(System.currentTimeMillis() - t1 + " ms");
        s.out.close();
    }

    public Solution() throws FileNotFoundException {
    }

    private static class InputReader {
        private final InputStream stream;
        private final byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        Random r = new Random();

        InputReader(final InputStream stream) {
            this.stream = stream;
        }

        InputReader(final String fileName) {
            InputStream stream = null;
            try {
                stream = new FileInputStream(fileName);
            } catch (final FileNotFoundException e) {
                e.printStackTrace();
            }
            this.stream = stream;
        }

        int[] nextArray(final int n) {
            final int[] arr = new int[n];
            for (int i = 0; i < n; i++)
                arr[i] = nextInt();
            return arr;
        }

        int[][] nextMatrix(final int n, final int m) {
            final int[][] matrix = new int[n][m];
            for (int i = 0; i < n; i++)
                for (int j = 0; j < m; j++)
                    matrix[i][j] = nextInt();
            return matrix;
        }

        String nextLine() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            final StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isEndOfLine(c));
            return res.toString();
        }

        String nextString() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            final StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isSpaceChar(c));
            return res.toString();
        }

        long nextLong() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        int nextInt() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        double nextDouble() {
            return Double.parseDouble(nextString());
        }

        private int read() {
            if (numChars == -1)
                throw new InputMismatchException();
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (final IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

        private boolean isSpaceChar(final int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        private boolean isEndOfLine(final int c) {
            return c == '\n' || c == '\r' || c == -1;
        }
    }

}