Monocarp has got an array a consisting of n integers. Let's denote k as the mathematic mean of these elements (note that it's possible that k is not an integer). 

The mathematic mean of an array of n elements is the sum of elements divided by the number of these elements (i. e. sum divided by n).

Monocarp wants to delete exactly two elements from a so that the mathematic mean of the remaining (n - 2) elements is still equal to k.

Your task is to calculate the number of pairs of positions [i, j] (i < j) such that if the elements on these positions are deleted, the mathematic mean of (n - 2) remaining elements is equal to k (that is, it is equal to the mathematic mean of n elements of the original array a).

Input

The first line contains a single integer t (1 ≤ t ≤ 10^4) — the number of testcases.

The first line of each testcase contains one integer n (3 ≤ n ≤ 2 ⋅ 10^5) — the number of elements in the array.

The second line contains a sequence of integers a_1, a_2, ..., a_n (0 ≤ a_i ≤ 10^{9}), where a_i is the i-th element of the array.

The sum of n over all testcases doesn't exceed 2 ⋅ 10^5.

Output

Print one integer — the number of pairs of positions [i, j] (i < j) such that if the elements on these positions are deleted, the mathematic mean of (n - 2) remaining elements is equal to k (that is, it is equal to the mathematic mean of n elements of the original array a).

Example

Input


4
4
8 8 8 8
3
50 20 10
5
1 4 7 3 5
7
1 2 3 4 5 6 7


Output


6
0
2
3

Note

In the first example, any pair of elements can be removed since all of them are equal.

In the second example, there is no way to delete two elements so the mathematic mean doesn't change.

In the third example, it is possible to delete the elements on positions 1 and 3, or the elements on positions 4 and 5.
1
3
228 1337 228

0

//   package faltu;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
//import java.security.KeyStore.Entry;
import java.util.*;
import java.util.Map.Entry;

public class Main {
    static long LowerBound(long[] a2, long x) { // x is the target value or key
	  int l=-1,r=a2.length;
	  while(l+1<r) {
	    int m=(l+r)>>>1;
	    if(a2[m]>=x) r=m;
	    else l=m;
	  }
	  return r;
	}
    static int UpperBound(int a[], int x) {// x is the key or target value
    int l=-1,r=a.length;
    while(l+1<r) {
       int m=(l+r)>>>1;
       if(a[m]<=x) l=m;
       else r=m;
    }
    return l+1;
 }
    public static long getClosest(long val1, long val2,long target)
	{
		if (target - val1 >= val2 - target)
		return val2;       
		else
		return val1;       
	}
    public static long findClosest(long arr[], long target)
    {
        int n = arr.length;
 
        // Corner cases
        if (target <= arr[0])
            return arr[0];
        if (target >= arr[n - 1])
            return arr[n - 1];
 
        // Doing binary search
        int i = 0, j = n, mid = 0;
        while (i < j) {
            mid = (i + j) / 2;
 
            if (arr[mid] == target)
                return arr[mid];
 
            /* If target is less than array element,
               then search in left */
            if (target < arr[mid]) {
        
                // If target is greater than previous
                // to mid, return closest of two
                if (mid > 0 && target > arr[mid - 1])
                    return getClosest(arr[mid - 1],
                                  arr[mid], target);
                 
                /* Repeat for left half */
                j = mid;             
            }
 
            // If target is greater than mid
            else {
                if (mid < n-1 && target < arr[mid + 1])
                    return getClosest(arr[mid],
                          arr[mid + 1], target);               
                i = mid + 1; // update i
            }
        }
 
        // Only single element left after search
        return arr[mid];
    }
    static void ruffleSort(long[] a) {
		int n=a.length;
		Random r=new Random();
		for (int i=0; i<a.length; i++) {
			long oi=r.nextInt(n), temp=a[i];
			a[i]=a[(int)oi];
			a[(int)oi]=temp;
		}
		Arrays.sort(a);
	}
    static void ruffleSort(int[] a) {
		int n=a.length;
		Random r=new Random();
		for (int i=0; i<a.length; i++) {
			int oi=r.nextInt(n), temp=a[i];
			a[i]=a[oi];
			a[oi]=temp;
		}
		Arrays.sort(a);
	}
    public static int findIndex(long arr[], long t) 
    { 
 
        // if array is Null 
        if (arr == null) { 
            return -1; 
        } 
 
        // find length of array 
        int len = arr.length; 
        int i = 0; 
 
        // traverse in the array 
        while (i < len) {
            if (arr[i] == t) { 
                return i; 
            } 
            else { 
                i = i + 1; 
            } 
        } 
        return -1; 
    }
 
    static long gcd(long a, long b)
    {
        if (a == 0)
            return b; 
        return gcd(b % a, a); 
    }
    static int gcd(int a, int b)
    {
        if (a == 0)
            return b; 
        return gcd(b % a, a); 
    }
    static long lcm(long a, long b)
    {
        return (a / gcd(a, b)) * b;
    }
 
    public static int[] swap(int a[], int left, int right)
    {
        int temp = a[left];
        a[left] = a[right];
        a[right] = temp;
        return a;
    }
    public static void swap(int max0,int max1)
    {
    	int temp=max0;
    	max0=max1;
    	max1=temp;
    }
 
    public static int[] reverse(int a[], int left, int right)
    {
 
        // Reverse the sub-array
        while (left < right) {
            int temp = a[left];
            a[left++] = a[right];
            a[right--] = temp;
        }
        return a;
    }
 
  
    static class FastReader {
        BufferedReader br;
        StringTokenizer st;
 
        public FastReader()
        {
            br = new BufferedReader(
                new InputStreamReader(System.in));
        }
 
        String next()
        {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                }
                catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
 
        int nextInt() { return Integer.parseInt(next()); }
 
        long nextLong() { return Long.parseLong(next()); }
 
        double nextDouble()
        {
            return Double.parseDouble(next());
        }
 
        String nextLine()
        {
            String str = "";
            try {
                str = br.readLine();
            }
            catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
    
//    *******----segement tree implement---******
    
//    -------------START--------------------------
    
    void buildTree (int[] arr,int[] tree,int start,int end,int treeNode)
    {
    	if(start==end)
    	{
    		tree[treeNode]=arr[start];
    		return;
    	}
    	buildTree(arr,tree,start,end,2*treeNode);
    	buildTree(arr,tree,start,end,2*treeNode+1);
    	tree[treeNode]=tree[treeNode*2]+tree[2*treeNode+1];
    }
    void updateTree(int[] arr,int[] tree,int start,int end,int treeNode,int idx,int value)
    {
    	if(start==end)
    	{
    		arr[idx]=value;
    		tree[treeNode]=value;
    		return;
    	}
    	int mid=(start+end)/2;
    	if(idx>mid)
    	{
    		updateTree(arr,tree,mid+1,end,2*treeNode+1,idx,value);
    	}
    	else
    	{
    		updateTree(arr,tree,start,mid,2*treeNode,idx,value);
    	}
    	tree[treeNode]=tree[2*treeNode]+tree[2*treeNode+1];
    }
    	static int[][] dp;
    	private static long getClosetNumberOfTarget(long[] dataArray, long target) {
    		 
    		// Edge case - Check if array length is zero
    		if (dataArray.length == 0)
    			System.exit(1);
    		// Straight case - If target is smaller or equal to first element in array
    		if (target <= dataArray[0])
    			return dataArray[0];
    		// Straight case - If target is greater or equal to last element in array
    		if (target >= dataArray[dataArray.length - 1])
    			return dataArray[dataArray.length - 1];
     
    		// Start binary search algorithm
    		int start = 0;
    		int end = dataArray.length-1;
    		int mid = 0;
     
    		// Keep dividing array till further division is not possible
    		while (end - start != 1) {
    			// Calculate middle index
    			mid = (start + end) / 2;
    			// Check if middle element is equal to target
    			if (target == dataArray[mid])
    				// If yes return middle element as middle element = target 
    				return dataArray[mid];
    			// Check if target is smaller to middle element. If yes, take first half of array including mid
    			if (target < dataArray[mid]) 
    				end = mid;
    			// Check if target is greater to middle element. If yes, take first half of array including mid
    			if (target > dataArray[mid])
    				start = mid;	
    		}
    		// Now you will have only two numbers in array in which target number will fall
    		return Math.abs(target - dataArray[start]) <= Math.abs(target - dataArray[end]) ? dataArray[start]
    				: dataArray[end];
    	}
    	private static int getClosetNumberOfTarget(int[] dataArray, int target) {
    		 
    		// Edge case - Check if array length is zero
    		if (dataArray.length == 0)
    			System.exit(1);
    		// Straight case - If target is smaller or equal to first element in array
    		if (target <= dataArray[0])
    			return dataArray[0];
    		// Straight case - If target is greater or equal to last element in array
    		if (target >= dataArray[dataArray.length - 1])
    			return dataArray[dataArray.length - 1];
     
    		// Start binary search algorithm
    		int start = 0;
    		int end = dataArray.length - 1;
    		int mid = 0;
     
    		// Keep dividing array till further division is not possible
    		while (start < end) {
    			// Calculate middle index
    			mid = (start + end) / 2;
    			// Check if middle element is equal to target
    			if (target == dataArray[mid])
    				// If yes return middle element as middle element = target
    				return dataArray[mid];
    			// Check if target is smaller to middle element. If yes, take first half of
    			// array including mid
    			if (target < dataArray[mid]) {
    				// If target is greater than previous element of middle element, we have reached the deciding range
    				if (target > dataArray[mid - 1])
    					return Math.abs(target - dataArray[mid]) >= Math.abs(target - dataArray[mid - 1]) ? dataArray[mid-1]
    							: dataArray[mid];
    				end = mid - 1;
    			}
    			// Check if target is greater to middle element. If yes, take first half of
    			// array including mid
    			if (target > dataArray[mid]) {
    				// If target is smaller than next element of middle element, we have reached the deciding range
    				if (target < dataArray[mid + 1])
    					return Math.abs(target - dataArray[mid]) <= Math.abs(target - dataArray[mid + 1]) ? dataArray[mid]
    							: dataArray[mid + 1];
     
    				start = mid + 1;
    			}
    		}
    		// after exiting form loop, middle element will be closer
    		return dataArray[mid];
    	}
    	
//    	disjoint set implementation --start
        static void makeSet(int n)
        {
        	parent=new int[n];
        	rank=new int[n];
        	for(int i=0;i<n;i++)
        	{
        		parent[i]=i;
        		rank[i]=0;
        	}
        	
        }
        static void union(int u,int v)
        {
        	u=findpar(u);
        	v=findpar(v);
        	if(rank[u]<rank[v])parent[u]=v;
        	else if(rank[v]<rank[u])parent[v]=u;
        	else 
        	{
//        		System.out.println(v+" "+parent[v]);
        		parent[v]=u;
//        		System.out.println(v+" "+parent[v]);
        		rank[u]++;
        	}
        }
        
    	private static int findpar(int node)
    	{	
    		if(node==parent[node])return node;
    		return parent[node]=findpar(parent[node]);
    	}
    	static int parent[];
        static int rank[];
    	
//    	*************end
    	static long MOD=(long) 1e+7;
        public static void main(String[] args)
        {
        	FastReader s = new FastReader();
	        dp=new int[1001][1001];
	        long tt = s.nextLong();
	        while (tt-->0)
	        {  
	        	 int n=s.nextInt();
	        	 int[] a=new int[n];
	        	 HashMap<Integer,Integer>map=new HashMap<>();
	        	 long sum=0;
	        	 for(int i=0;i<n;i++)
	        	 {
	        		 a[i]=s.nextInt();
	        		 sum+=a[i];
	        	 }
	        	 sum*=2;
	        	 if(sum%n!=0)System.out.println("0");
	        	 else
	        	 {
	        		 sum/=n;
	        		 long cnt=0;
	        		 for(int i=0;i<n;i++)
	        		 {
	        			 int x=(int) (sum-a[i]);
	        			 if(map.containsKey(x))cnt+=map.get(x);
	        			 map.put(a[i], map.getOrDefault(a[i], 0)+1);
	        		 }
	        		 System.out.println(cnt);
	        	 }
	        }
        }
        static boolean issafe(int i, int j, int r,int c, char ch)
        {
			if (i < 0 || j < 0 || i >= r || j >= c|| ch!= '1')return false;
			else return true;
        }
        static long power(long a, long b)
        {
        	   a %=MOD;
        	    long out = 1;
        	    while (b > 0) {
        	        if((b&1)!=0)out = out * a % MOD;
        	        a = a * a % MOD;
        	        b >>= 1;
        			a*=a;
        	    }
        	    return out;
        }
//        static long power(long x, long y)
//        {
//            long res = 1;     // Initialize result
//          
//            while (y > 0)
//            {
//               
//                // If y is odd, multiply x with result
//                if ((y & 1) != 0)
//                    res = res * x;
//          
//                // y must be even now
//                y = y >> 1; // y = y/2
//                x = x * x;  // Change x to x^2
//            }
//            return res;
//        }

		static boolean check(String str)
        {
            // Compute sum of digits
            int n = str.length();
            int digitSum = 0;
            for (int i=0; i<n; i++)
                digitSum += (str.charAt(i)-'0');
          
            // Check if sum of digits is
            // divisible by 3.
            return (digitSum % 3 == 0);
        }

}
class pair{
	long x,y;
	public pair(long x,long y)
	{
		this.x=x;
		this.y=y;
	}
}



