Highway 201 is the most busy street in Rockport. Traffic cars cause a lot of hindrances to races, especially when there are a lot of them. The track which passes through this highway can be divided into n sub-tracks. You are given an array a where a_i represents the number of traffic cars in the i-th sub-track. You define the inconvenience of the track as ∑_{i=1}^{n} ∑_{j=i+1}^{n} \lvert a_i-a_j\rvert, where |x| is the absolute value of x. 

You can perform the following operation any (possibly zero) number of times: choose a traffic car and move it from its current sub-track to any other sub-track.

Find the minimum inconvenience you can achieve.

Input

The first line of input contains a single integer t (1≤ t≤ 10 000) — the number of test cases.

The first line of each test case contains a single integer n (1≤ n≤ 2⋅ 10^5).

The second line of each test case contains n integers a_1, a_2, …, a_n (0≤ a_i≤ 10^9).

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

Output

For each test case, print a single line containing a single integer: the minimum inconvenience you can achieve by applying the given operation any (possibly zero) number of times.

Example

Input


3
3
1 2 3
4
0 1 1 0
10
8 3 6 11 5 2 1 7 10 4


Output


0
4
21

Note

For the first test case, you can move a car from the 3-rd sub-track to the 1-st sub-track to obtain 0 inconvenience.

For the second test case, moving any car won't decrease the inconvenience of the track.
/*Everything is Hard 
 * Before Easy 
 * Jai Mata Dii 
 */ 
 
import java.util.*; 
import java.io.*; 
  
public class Main { 
	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; }} 
	static long mod = (long)(1e9+7); 
	// static long mod = 998244353; 
//	 static Scanner sc = new Scanner(System.in); 
	static FastReader sc = new FastReader(); 
	static PrintWriter out = new PrintWriter(System.out);
	public static void main (String[] args) { 
		int t = 1;
		t = sc.nextInt();
		z :for(int tc=1;tc<=t;tc++){
			int n = sc.nextInt();
			long a[] = new long[n];
			long sum = 0;
			for(int i=0;i<n;i++) {
				a[i] = sc.nextInt();
				sum += a[i];
			}
			long rem = sum%n;
			long div = sum/n;
			long ext = rem;
			long ans = ext*(n-ext);
			out.write(ans+"\n");
	    }
		out.close();
	}
	static long gcd(long a,long b) { if(b==0) return a; return gcd(b,a%b); } 
	private static void sort(int[] a) {List<Integer> k = new ArrayList<>();for(int val : a) k.add(val);Collections.sort(k);for(int i=0;i<a.length;i++) a[i] = k.get(i);} 
	private static void ini(List<Integer>[] tre2){for(int i=0;i<tre2.length;i++){tre2[i] = new ArrayList<>();}} 
	private static void init(List<int[]>[] tre2){for(int i=0;i<tre2.length;i++){tre2[i] = new ArrayList<>();}} 
	private static void sort(long[] a) {List<Long> k = new ArrayList<>();for(long val : a) k.add(val);Collections.sort(k);for(int i=0;i<a.length;i++) a[i] = k.get(i);} 
}