Tam woke up bored, so he decided to create an interesting array with his friend Nhan. Now, they have an array a of n positive integers, Tam will choose a number ai and Nhan will choose a number aj. Count the number of interesting pairs (ai, aj) that meet all the following conditions:

• 1 ≤ i, j ≤ n;
• i ≠ j;
• The absolute difference |~a_i~ - ~a_j~| must be equal to the maximum absolute difference over all the pairs in the array. More formally, |~a_i~ - ~a_j~| = max~_{1 ≤ p,q ≤ n}~ |~a_p~ - ~a_q~|.

Input Format

• The input consists of multiple test cases. The first line contains a single integer t (1 ≤ t ≤ 100), which denotes the number of test cases. Description of the test cases follows.
• The first line of each test case contains an integer n (2 ≤ n ≤ 105).The second line of each test case contains n integers a1, a2, …,an (1 ≤ ai ≤ 105).
• It is guaranteed that the sum of n over all test cases does not exceed 105.

Output Format

For each test case print an integer - the number of interesting pairs (ai,aj).

For example

Input Format

2
5
6 2 3 8 1
6
7 2 8 3 2 10

Output Format

2
4

Note

In the first example, the two ways are:

• Tam chooses the fourth number 8 and Nhan chooses the fifth number 1.

• Tam chooses the fifth number 1 and Nhan chooses the fourth number 8.

  In the second example, the four ways are:

• Tam chooses the second number 2 and Nhan chooses the sixth number 10.

• Tam chooses the sixth number 10 and Nhan chooses the second number 2.
• Tam chooses the fifth number 2 and Nhan chooses the sixth number 10.
• Tam chooses the sixth number 10 and Nhan chooses the fifth number 2