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

#include <bits/stdc++.h>
using namespace std;
const long long MAXN = 2e5 + 5;
const long long SQRTN = 1003;
const long long LOGN = 22;
const double PI = acos(-1);
const long long INF = 1e18;
const long long MOD = 1e9 + 7;
const long long FMOD = 998244353;
const double eps = 1e-9;
void __print(long long x) { cerr << x; }
void __print(long x) { cerr << x; }
void __print(unsigned x) { cerr << x; }
void __print(unsigned long x) { cerr << x; }
void __print(unsigned long long x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char *x) { cerr << '\"' << x << '\"'; }
void __print(const string &x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }
template <typename T, typename V>
void __print(const pair<T, V> &x) {
  cerr << '{';
  __print(x.first);
  cerr << ',';
  __print(x.second);
  cerr << '}';
}
template <typename T>
void __print(const T &x) {
  long long f = 0;
  cerr << '{';
  for (auto &i : x) cerr << (f++ ? "," : ""), __print(i);
  cerr << "}";
}
void _print() { cerr << "]\n"; }
template <typename T, typename... V>
void _print(T t, V... v) {
  __print(t);
  if (sizeof...(v)) cerr << ", ";
  _print(v...);
}
mt19937 RNG(chrono::steady_clock::now().time_since_epoch().count());
template <typename T>
T gcd(T a, T b) {
  if (b == 0) return a;
  a %= b;
  return gcd(b, a);
}
template <typename T>
T lcm(T a, T b) {
  return (a * (b / gcd(a, b)));
}
long long add(long long a, long long b, long long c = MOD) {
  long long res = a + b;
  return (res >= c ? res % c : res);
}
long long sub(long long a, long long b, long long c = MOD) {
  long long res;
  if (abs(a - b) < c)
    res = a - b;
  else
    res = (a - b) % c;
  return (res < 0 ? res + c : res);
}
long long mul(long long a, long long b, long long c = MOD) {
  long long res = (long long)a * b;
  return (res >= c ? res % c : res);
}
long long muln(long long a, long long b, long long c = MOD) {
  long long res = (long long)a * b;
  return ((res % c) + c) % c;
}
long long mulmod(long long a, long long b, long long m = MOD) {
  long long q = (long long)(((long double)a * (long double)b) / (long double)m);
  long long r = a * b - q * m;
  if (r > m) r %= m;
  if (r < 0) r += m;
  return r;
}
template <typename T>
T binpow(T e, T n) {
  T x = 1, p = e;
  while (n) {
    if (n & 1) x = x * p;
    p = p * p;
    n >>= 1;
  }
  return x;
}
template <typename T>
T binpow2(T e, T n, T m = MOD) {
  T x = 1, p = e;
  while (n) {
    if (n & 1) x = mul(x, p, m);
    p = mul(p, p, m);
    n >>= 1;
  }
  return x;
}
template <typename T>
T extended_euclid(T a, T b, T &x, T &y) {
  T xx = 0, yy = 1;
  y = 0;
  x = 1;
  while (b) {
    T q = a / b, t = b;
    b = a % b;
    a = t;
    t = xx;
    xx = x - q * xx;
    x = t;
    t = yy;
    yy = y - q * yy;
    y = t;
  }
  return a;
}
template <typename T>
T mod_inverse(T a, T n = MOD) {
  T x, y, z = 0;
  T d = extended_euclid(a, n, x, y);
  return (d > 1 ? -1 : sub(x, z, n));
}
const long long FACSZ = 1e4;
long long fact[FACSZ], ifact[FACSZ];
void precom(long long c = MOD) {
  fact[0] = 1;
  for (long long i = 1; i < FACSZ; i++) fact[i] = mul(fact[i - 1], i, c);
  ifact[FACSZ - 1] = mod_inverse(fact[FACSZ - 1], c);
  for (long long i = FACSZ - 1 - 1; i >= 0; i--) {
    ifact[i] = mul(i + 1, ifact[i + 1], c);
  }
}
vector<long long> primes;
void prime_precom() {
  primes.push_back(2);
  for (long long x = 3; primes.size() <= MAXN; x += 2) {
    bool isPrime = true;
    for (auto p : primes) {
      if (x % p == 0) {
        isPrime = false;
        break;
      }
      if (p * p > x) {
        break;
      }
    }
    if (isPrime) {
      primes.push_back(x);
    }
  }
}
long long ncr(long long n, long long k) {
  if (n < k) return 0;
  if (k == 0) return 1;
  long long res = 1;
  if (k > n - k) k = n - k;
  for (long long i = 0; i < k; ++i) {
    res *= (n - i);
    res /= (i + 1);
  }
  return res;
}
long long ncr_modp(long long n, long long k, long long c = MOD) {
  if (n < k) return 0;
  if (k == 0) return 1;
  long long res = 1;
  if (k > n - k) k = n - k;
  for (long long i = 0; i < k; ++i) {
    res = mul(res, n - i, c);
    res = mul(res, binpow2(i + 1, c - 2, c), c);
  }
  return res;
}
vector<long long> factors;
void factorize(long long a) {
  factors.clear();
  for (long long i = 1; i * i <= a; i++) {
    if (a % i == 0) {
      factors.push_back(i);
      factors.push_back(a / i);
    }
  }
  sort(factors.begin(), factors.end());
}
long long ncr_precom(long long n, long long r, long long c = MOD) {
  return mul(mul(ifact[r], ifact[n - r], c), fact[n], c);
}
long long ceil(long long a, long long b) { return (a + b - 1) / b; }
bool is_prime(long long n) {
  for (long long i = 2; i * i <= n; i++) {
    if (n % i == 0) {
      return 0;
    }
  }
  return 1;
}
bool diophantine_checker(long long a, long long b, long long n) {
  for (long long i = 0; i * a <= n; i++) {
    if ((n - (i * a)) % b == 0) {
      return true;
    }
  }
  return false;
}
long long count_divisors(long long n) {
  long long c;
  long long ans = 1;
  for (long long i = 2; i * i <= n; i++) {
    c = 0;
    while (n % i == 0) {
      c++;
      n /= i;
    }
    ans *= (c + 1);
  }
  if (n > 2) {
    return ans * 2;
  }
  return ans;
}
string to_binary(long long n) {
  string r;
  while (n != 0) {
    r = (n % 2 == 0 ? "0" : "1") + r;
    n /= 2;
  }
  return r;
}
bool ispower2(long long x) { return x && (!(x & (x - 1))); }
vector<long long> spf;
void sieve() {
  spf.resize(MAXN);
  spf[1] = 1;
  for (long long i = 2; i < MAXN; i++) {
    spf[i] = i;
  }
  for (long long i = 4; i < MAXN; i += 2) {
    spf[i] = 2;
  }
  for (long long i = 3; i * i <= MAXN; i++) {
    if (spf[i] == i) {
      for (long long j = i * i; j < MAXN; j += i) {
        if (spf[j] == j) {
          spf[j] = i;
        }
      }
    }
  }
}
void pfactor(long long x, vector<long long> &ret) {
  while (x != 1) {
    ret.push_back(spf[x]);
    x = x / spf[x];
  }
}
void solvethetestcase() {
  long long n;
  cin >> n;
  vector<long long> v(n);
  map<long long, long long> make_pair;
  long long sm = 0;
  for (long long i = 0; i < n; i++) {
    cin >> v[i];
    sm += v[i];
    make_pair[v[i]]++;
  }
  if ((sm * 2) % n) {
    cout << 0 << "\n";
    return;
  }
  long long x = (sm * 2) / n;
  long long ans = 0;
  for (long long i = 0; i < n; i++) {
    if (make_pair[v[i]] == 1) {
      make_pair.erase(v[i]);
    } else {
      make_pair[v[i]]--;
    }
    auto it = make_pair.find(x - v[i]);
    if (it != make_pair.end()) {
      ans += it->second;
    }
  }
  cout << ans << "\n";
}
signed main() {
  cout << fixed << setprecision(12);
  ;
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long t = 1;
  cin >> t;
  for (long long testcase = 1; testcase < t + 1; testcase++) {
    solvethetestcase();
  }
}
