#include <bits/stdc++.h>
using namespace std;
void ac(long long x) {
  if (x)
    puts("YES");
  else
    puts("NO");
}
long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
long long ppow(long long a, long long b, long long mod) {
  a %= mod;
  long long ans = 1 % mod;
  while (b) {
    if (b & 1) ans = (long long)ans * a % mod;
    a = (long long)a * a % mod;
    b >>= 1;
  }
  return ans;
}
long long readdd() {
  long long x = 0, f = 1;
  char c = getchar();
  while (!isdigit(c) && c != '-') c = getchar();
  if (c == '-') f = -1, c = getchar();
  while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
  return f * x;
}
void printtt(long long x) {
  if (x < 0) putchar('-'), x = -x;
  if (x >= 10) printtt(x / 10);
  putchar(x % 10 + '0');
}
bool addd(long long a, long long b) { return a > b; }
long long lowbit(long long x) { return x & -x; }
const long long dx[4] = {0, 0, 1, -1};
const long long dy[4] = {1, -1, 0, 0};
const long long BN = 2e6 + 5;
struct BIT {
  long long c[BN];
  void init() { memset(c, 0, sizeof c); }
  long long lowbit(long long i) { return i & -i; }
  void add(long long i, long long t) {
    while (i < BN) c[i] += t, i += lowbit(i);
  }
  long long ask(long long i) {
    long long ans = 0;
    while (i) ans += c[i], i -= lowbit(i);
    return ans;
  }
};
bool Isprime(long long x) {
  for (long long i = 2; i * i <= x; i++)
    if (x % i == 0) return 0;
  return 1;
}
void init() { ; }
const double Pi = acos(-1);
const double eps = 1e-7;
const long long mod = 1e9 + 7;
const long long modd = mod - 1;
const long long maxm = 2e6 + 5;
vector<long long> l[maxm], r[maxm];
long long a[maxm];
long long b[maxm];
long long n;
void solve() {
  n = readdd();
  for (signed long long(i) = 1; (i) <= (n); (i)++) a[i] = readdd();
  for (signed long long(i) = 1; (i) <= (n); (i)++) {
    l[i].clear();
    r[i].clear();
  }
  for (signed long long(i) = 1; (i) <= (n); (i)++) {
    for (long long j = i + 1; j <= n; j++) {
      if (a[i] == a[j]) {
        r[i].push_back(j);
        l[j].push_back(i);
      }
    }
  }
  for (signed long long(i) = 1; (i) <= (n); (i)++) {
    sort(l[i].begin(), l[i].end());
    sort(r[i].begin(), r[i].end());
  }
  long long ans = 0;
  for (long long i = 1; i <= n; i++) {
    for (long long j = i + 1; j <= n; j++) {
      long long len1 = lower_bound(l[j].begin(), l[j].end(), i) - l[j].begin();
      long long len2 = upper_bound(r[i].begin(), r[i].end(), j) - r[i].begin();
      len2 = (long long)r[i].size() - len2;
      ans += len1 * len2;
    }
  }
  printtt(ans);
  puts("");
  ;
}
signed main() {
  init();
  signed QP;
  scanf("%d", &QP);
  while (QP--) solve();
  return 0;
}

### Prompt

Please formulate a Cpp solution to the following problem:

You are given an array a_1, a_2 ... a_n. Calculate the number of tuples (i, j, k, l) such that: 

  * 1 ≤ i < j < k < l ≤ n; 
  * a_i = a_k and a_j = a_l; 

Input

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

The first line of each test case contains a single integer n (4 ≤ n ≤ 3000) — the size of the array a.

The second line of each test case contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ n) — the array a.

It's guaranteed that the sum of n in one test doesn't exceed 3000.

Output

For each test case, print the number of described tuples.

Example

Input


2
5
2 2 2 2 2
6
1 3 3 1 2 3


Output


5
2

Note

In the first test case, for any four indices i < j < k < l are valid, so the answer is the number of tuples.

In the second test case, there are 2 valid tuples: 

  * (1, 2, 4, 6): a_1 = a_4 and a_2 = a_6; 
  * (1, 3, 4, 6): a_1 = a_4 and a_3 = a_6. 

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
void ac(long long x) {
  if (x)
    puts("YES");
  else
    puts("NO");
}
long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
long long ppow(long long a, long long b, long long mod) {
  a %= mod;
  long long ans = 1 % mod;
  while (b) {
    if (b & 1) ans = (long long)ans * a % mod;
    a = (long long)a * a % mod;
    b >>= 1;
  }
  return ans;
}
long long readdd() {
  long long x = 0, f = 1;
  char c = getchar();
  while (!isdigit(c) && c != '-') c = getchar();
  if (c == '-') f = -1, c = getchar();
  while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
  return f * x;
}
void printtt(long long x) {
  if (x < 0) putchar('-'), x = -x;
  if (x >= 10) printtt(x / 10);
  putchar(x % 10 + '0');
}
bool addd(long long a, long long b) { return a > b; }
long long lowbit(long long x) { return x & -x; }
const long long dx[4] = {0, 0, 1, -1};
const long long dy[4] = {1, -1, 0, 0};
const long long BN = 2e6 + 5;
struct BIT {
  long long c[BN];
  void init() { memset(c, 0, sizeof c); }
  long long lowbit(long long i) { return i & -i; }
  void add(long long i, long long t) {
    while (i < BN) c[i] += t, i += lowbit(i);
  }
  long long ask(long long i) {
    long long ans = 0;
    while (i) ans += c[i], i -= lowbit(i);
    return ans;
  }
};
bool Isprime(long long x) {
  for (long long i = 2; i * i <= x; i++)
    if (x % i == 0) return 0;
  return 1;
}
void init() { ; }
const double Pi = acos(-1);
const double eps = 1e-7;
const long long mod = 1e9 + 7;
const long long modd = mod - 1;
const long long maxm = 2e6 + 5;
vector<long long> l[maxm], r[maxm];
long long a[maxm];
long long b[maxm];
long long n;
void solve() {
  n = readdd();
  for (signed long long(i) = 1; (i) <= (n); (i)++) a[i] = readdd();
  for (signed long long(i) = 1; (i) <= (n); (i)++) {
    l[i].clear();
    r[i].clear();
  }
  for (signed long long(i) = 1; (i) <= (n); (i)++) {
    for (long long j = i + 1; j <= n; j++) {
      if (a[i] == a[j]) {
        r[i].push_back(j);
        l[j].push_back(i);
      }
    }
  }
  for (signed long long(i) = 1; (i) <= (n); (i)++) {
    sort(l[i].begin(), l[i].end());
    sort(r[i].begin(), r[i].end());
  }
  long long ans = 0;
  for (long long i = 1; i <= n; i++) {
    for (long long j = i + 1; j <= n; j++) {
      long long len1 = lower_bound(l[j].begin(), l[j].end(), i) - l[j].begin();
      long long len2 = upper_bound(r[i].begin(), r[i].end(), j) - r[i].begin();
      len2 = (long long)r[i].size() - len2;
      ans += len1 * len2;
    }
  }
  printtt(ans);
  puts("");
  ;
}
signed main() {
  init();
  signed QP;
  scanf("%d", &QP);
  while (QP--) solve();
  return 0;
}

```