This is the easy version of this problem. The only difference between easy and hard versions is the constraints on k and m (in this version k=2 and m=3). Also, in this version of the problem, you DON'T NEED to output the answer by modulo.

You are given a sequence a of length n consisting of integers from 1 to n. The sequence may contain duplicates (i.e. some elements can be equal).

Find the number of tuples of m = 3 elements such that the maximum number in the tuple differs from the minimum by no more than k = 2. Formally, you need to find the number of triples of indices i < j < z such that

$$$max(a_i, a_j, a_z) - min(a_i, a_j, a_z) ≤ 2.$$$

For example, if n=4 and a=[1,2,4,3], then there are two such triples (i=1, j=2, z=4 and i=2, j=3, z=4). If n=4 and a=[1,1,1,1], then all four possible triples are suitable.

Input

The first line contains a single integer t (1 ≤ t ≤ 2 ⋅ 10^5) — the number of test cases. Then t test cases follow.

The first line of each test case contains an integer n (1 ≤ n ≤ 2 ⋅ 10^5) — the length of the sequence a.

The next line contains n integers a_1, a_2,…, a_n (1 ≤ a_i ≤ n) — the sequence a.

It is guaranteed that the sum of n for all test cases does not exceed 2 ⋅ 10^5.

Output

Output t answers to the given test cases. Each answer is the required number of triples of elements, such that the maximum value in the triple differs from the minimum by no more than 2. Note that in difference to the hard version of the problem, you don't need to output the answer by modulo. You must output the exact value of the answer.

Example

Input


4
4
1 2 4 3
4
1 1 1 1
1
1
10
5 6 1 3 2 9 8 1 2 4


Output


2
4
0
15
import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.ListIterator;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

import javax.swing.text.html.HTMLDocument.Iterator;

/*
 * Printing Euler Tour in an Eulerian Graph
 */
public class D {

	static class pair implements Comparable<pair> {
		int x;
		int y;

		public pair(int d, int u) {
			x = d;
			y = u;
		}

		@Override
		public int compareTo(pair o) {
//			// TODO Auto-generated method stub
//			if (y == o.y)
//				return x - o.x;
			return 0;
		}

	}

	static ArrayList<Integer>[] adjList;
	static LinkedList<Integer> tour;
	static ArrayList<Integer>[] g;

	static ArrayList<Integer> primes; // generated by sieve

	/*
	 * 1. Generating a list of prime factors of N
	 */
	static HashMap<Integer, Integer> primeFactors(int N) // O(sqrt(N) / ln sqrt(N))
	{
		HashMap<Integer, Integer> factors = new HashMap<>(); // take abs(N) in case of -ve integers
		int idx = 0, p = primes.get(idx);

		while (p * p <= N) {
			int c = 0;
			while (N % p == 0) {
				N /= p;
				c++;
			}
			if (c > 0)
				factors.put(p, c);
			if (idx + 1 == primes.size())
				break;
			p = primes.get(++idx);
		}

		if (N != 1) // last prime factor may be > sqrt(N)
			factors.put(N, 1); // for integers whose largest prime factor has a power of 1
		return factors;
	}

	static int[] isComposite;

	static void sieve(int N) // O(N log log N)
	{
		isComposite = new int[N + 1];
		isComposite[0] = isComposite[1] = 1; // 0 indicates a prime number
		primes = new ArrayList<Integer>();

		for (int i = 2; i <= N; ++i) // can loop till i*i <= N if primes array is not needed O(N log log sqrt(N))
			if (isComposite[i] == 0) // can loop in 2 and odd integers for slightly better performance
			{
				primes.add(i);
				if (1l * i * i <= N)
					for (int j = i * i; j <= N; j += i) // j = i * 2 will not affect performance too much, may alter in
														// modified sieve
						isComposite[j] = 1;
			}
	}

	static HashSet<Integer> hs;
	static int[] a;
	static long[] cum;

	static void divide(int s, int e) {
//		System.out.println(s + " " + e);
		if (e == -1 || s > e)
			return;
		if (cum[e + 1] - cum[s] <= 1e9)
			hs.add((int) (cum[e + 1] - cum[s]));
//		System.out.println(cum[e + 1] - cum[s]);
		if (e == s)
			return;
		int temp = a[e] + a[s] >> 1;
		int lo = s;
		int hi = e;
		int ans = -1;
		while (lo <= hi) {
			int mid = lo + hi >> 1;
			if (a[mid] <= temp) {
				ans = mid;
				lo = mid + 1;
			} else
				hi = mid - 1;
		}
		if (ans == -1 || ans == e)
			return;
		divide(s, ans);
		divide(ans + 1, e);
	}

	public static void main(String[] args) throws IOException, InterruptedException {
		Scanner sc = new Scanner(System.in);
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		PrintWriter pw = new PrintWriter(System.out);
//		Scanner sc = new Scanner("input.txt");
//		PrintWriter pw = new PrintWriter("output.txt");
		init();
		int t = Integer.parseInt(br.readLine());
		while (t-- > 0) {
			st = new StringTokenizer(br.readLine());
			int n = Integer.parseInt(st.nextToken());
			int m = 3;
			int k = 2;

			int[] cum = new int[n + 1];
			Integer[] a = new Integer[n];
			st = new StringTokenizer(br.readLine());
			for (int i = 0; i < a.length; i++) {
				a[i] = Integer.parseInt(st.nextToken());
//				cum[i+1]=cum[i]-a[i];
			}

			Arrays.sort(a);
			long ans = 0;
			for (int i = m - 1; i < a.length; i++) {
				int s = 0;
				int e = i;
				int temp = -1;
				while (s <= e) {
					int mid = s + e >> 1;
					if (a[i] - a[mid] <= k) {
						e = mid - 1;
						temp = mid;
					} else
						s = mid + 1;
				}
				int count = i - temp;
//				System.out.println(i+" "+temp+" "+fac[3]);
				if (count >= m - 1) {
//					System.out.println( count * 1l * (count - 1) / 2);
					ans += count * 1l * (count - 1) / 2;
				}
			}

			pw.println(ans);

		}

		pw.flush();
	}

	static int power(int x, int y, int p) {

		// Initialize result
		int 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 = (int) ((res * 1l * x) % p);

			// y must be even now
			y = y >> 1; // y = y/2
			x = (int) ((x * 1l * x) % p);
		}

		return res;
	}

	// Returns n^(-1) mod p
	static int modInverse(int n, int p) {
		return power(n, p - 2, p);
	}

	// Returns nCr % p using Fermat's
	// little theorem.
	static int nCrModPFermat(int n, int r, int 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
		return (int) (((fac[n] * 1l * modInverse(fac[r], p)) % p * modInverse(fac[n - r], p) % p) % p);
	}

	static int[] fac;

	static void init() {
		fac = new int[200001];
		fac[0] = 1;
		for (int i = 1; i <= 200000; i++)
			fac[i] = (int) ((fac[i - 1] * 1l * i) % mod);
	}

	static int mod = 1000000007;
	static long ans = 10000000000l;

	static void find(int i, int sum, String s, int t) {
		if (sum == t) {
			ans = Math.min(ans, Integer.parseInt(s));
			return;
		}
//		System.out.println(s);
		if (i == 0)
			return;
		find(i - 1, sum, s, t);
		find(i - 1, sum + i, i + s, t);

	}

	static class Scanner {
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream s) {
			br = new BufferedReader(new InputStreamReader(s));
		}

		public Scanner(String s) throws FileNotFoundException {
			br = new BufferedReader(new FileReader(new File(s)));
		}

		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}

		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}

		public String nextLine() throws IOException {
			return br.readLine();
		}

		public boolean ready() throws IOException {
			return br.ready();
		}

	}
}