#include <bits/stdc++.h>
using namespace std;
const int maxn = 3005;
const int maxm = 1000005;
const int inf = 2147483647;
const double eps = 1e-9;
const long long INF = 9223372036854775807ll;
long long qpow(long long a, long long b, long long c) {
  long long ans = 1;
  while (b) {
    if (b & 1) ans = ans * a % c;
    a = a * a % c;
    b >>= 1;
  }
  return ans;
}
inline void rd(int *x) {
  int k, m = 0;
  *x = 0;
  for (;;) {
    (k) = getchar();
    if (k == '-') {
      m = 1;
      break;
    }
    if ('0' <= k && k <= '9') {
      *x = k - '0';
      break;
    }
  }
  for (;;) {
    (k) = getchar();
    if (k < '0' || k > '9') break;
    *x = (*x) * 10 + k - '0';
  }
  if (m) (*x) = -(*x);
}
inline void rd(long long *x) {
  int k, m = 0;
  *x = 0;
  for (;;) {
    (k) = getchar();
    if (k == '-') {
      m = 1;
      break;
    }
    if ('0' <= k && k <= '9') {
      *x = k - '0';
      break;
    }
  }
  for (;;) {
    (k) = getchar();
    if (k < '0' || k > '9') break;
    *x = (*x) * 10 + k - '0';
  }
  if (m) (*x) = -(*x);
}
inline void rd(double *x) { scanf("%lf", x); }
inline int rd(char c[]) {
  int i, s = 0;
  for (;;) {
    (i) = getchar();
    if (i != ' ' && i != '\n' && i != '\r' && i != '\t' && i != EOF) break;
  }
  c[s++] = i;
  for (;;) {
    (i) = getchar();
    if (i == ' ' || i == '\n' || i == '\r' || i == '\t' || i == EOF) break;
    c[s++] = i;
  }
  c[s] = '\0';
  return s;
}
inline void rd(int a[], int n) {
  for (register int i = (0); i < (n); ++i) rd(&a[i]);
}
inline void rd(long long a[], int n) {
  for (register int i = (0); i < (n); ++i) rd(&a[i]);
}
template <class T, class S>
inline void rd(T *x, S *y) {
  rd(x);
  rd(y);
}
template <class T, class S, class U>
inline void rd(T *x, S *y, U *z) {
  rd(x);
  rd(y);
  rd(z);
}
template <class T, class S, class U, class V>
inline void rd(T *x, S *y, U *z, V *w) {
  rd(x);
  rd(y);
  rd(z);
  rd(w);
}
inline void wr(int x) {
  if (x < 10)
    putchar('0' + x);
  else
    wr(x / 10), wr(x % 10);
}
inline void wr(int x, char c) {
  int s = 0, m = 0;
  char f[10];
  if (x < 0) m = 1, x = -x;
  while (x) f[s++] = x % 10, x /= 10;
  if (!s) f[s++] = 0;
  if (m) putchar('-');
  while (s--) putchar(f[s] + '0');
  putchar(c);
}
inline void wr(long long x, char c) {
  int s = 0, m = 0;
  char f[20];
  if (x < 0) m = 1, x = -x;
  while (x) f[s++] = x % 10, x /= 10;
  if (!s) f[s++] = 0;
  if (m) putchar('-');
  while (s--) putchar(f[s] + '0');
  putchar(c);
}
inline void wr(double x, char c) {
  printf("%.15f", x);
  putchar(c);
}
inline void wr(const char c[]) {
  int i;
  for (i = 0; c[i] != '\0'; i++) putchar(c[i]);
}
inline void wr(const char x[], char c) {
  int i;
  for (i = 0; x[i] != '\0'; i++) putchar(x[i]);
  putchar(c);
}
template <class T>
inline void wrn(T x) {
  wr(x, '\n');
}
template <class T, class S>
inline void wrn(T x, S y) {
  wr(x, ' ');
  wr(y, '\n');
}
template <class T, class S, class U>
inline void wrn(T x, S y, U z) {
  wr(x, ' ');
  wr(y, ' ');
  wr(z, '\n');
}
template <class T, class S, class U, class H>
inline void wrn(T x, S y, U z, H h) {
  wr(x, ' ');
  wr(y, ' ');
  wr(z, ' ');
  wr(h, '\n');
}
template <class T>
inline void wra(T x[], int n) {
  int i;
  if (!n) {
    putchar('\n');
    return;
  }
  for (register int i = (0); i < (n - 1); ++i) wr(x[i], ' ');
  wr(x[n - 1], '\n');
}
int a[maxn], cnt[maxn][maxn];
int main() {
  int t;
  rd(&t);
  while (t--) {
    int n;
    rd(&n);
    rd(a + 1, n);
    for (register int i = (1); i < (n + 1); ++i) {
      for (register int j = (1); j < (n + 1); ++j) cnt[i][j] = cnt[i - 1][j];
      cnt[i][a[i]]++;
    }
    long long ans = 0, as = 0;
    for (register int i = (1); i < (n + 1); ++i) {
      as = 0;
      for (register int j = (i + 1); j < (n); ++j) {
        as += 1ll * (cnt[j][a[j]] - cnt[i][a[j]]) *
                  (cnt[n][a[j]] - cnt[j][a[j]]) -
              1ll * (cnt[j - 1][a[j]] - cnt[i][a[j]]) *
                  (cnt[n][a[j]] - cnt[j - 1][a[j]]);
        if (a[i] != a[j + 1]) continue;
        ans += as - (cnt[j][a[j + 1]] - cnt[i][a[j + 1]]);
      }
    }
    wrn(ans);
  }
}

### Prompt

Generate 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;
const int maxn = 3005;
const int maxm = 1000005;
const int inf = 2147483647;
const double eps = 1e-9;
const long long INF = 9223372036854775807ll;
long long qpow(long long a, long long b, long long c) {
  long long ans = 1;
  while (b) {
    if (b & 1) ans = ans * a % c;
    a = a * a % c;
    b >>= 1;
  }
  return ans;
}
inline void rd(int *x) {
  int k, m = 0;
  *x = 0;
  for (;;) {
    (k) = getchar();
    if (k == '-') {
      m = 1;
      break;
    }
    if ('0' <= k && k <= '9') {
      *x = k - '0';
      break;
    }
  }
  for (;;) {
    (k) = getchar();
    if (k < '0' || k > '9') break;
    *x = (*x) * 10 + k - '0';
  }
  if (m) (*x) = -(*x);
}
inline void rd(long long *x) {
  int k, m = 0;
  *x = 0;
  for (;;) {
    (k) = getchar();
    if (k == '-') {
      m = 1;
      break;
    }
    if ('0' <= k && k <= '9') {
      *x = k - '0';
      break;
    }
  }
  for (;;) {
    (k) = getchar();
    if (k < '0' || k > '9') break;
    *x = (*x) * 10 + k - '0';
  }
  if (m) (*x) = -(*x);
}
inline void rd(double *x) { scanf("%lf", x); }
inline int rd(char c[]) {
  int i, s = 0;
  for (;;) {
    (i) = getchar();
    if (i != ' ' && i != '\n' && i != '\r' && i != '\t' && i != EOF) break;
  }
  c[s++] = i;
  for (;;) {
    (i) = getchar();
    if (i == ' ' || i == '\n' || i == '\r' || i == '\t' || i == EOF) break;
    c[s++] = i;
  }
  c[s] = '\0';
  return s;
}
inline void rd(int a[], int n) {
  for (register int i = (0); i < (n); ++i) rd(&a[i]);
}
inline void rd(long long a[], int n) {
  for (register int i = (0); i < (n); ++i) rd(&a[i]);
}
template <class T, class S>
inline void rd(T *x, S *y) {
  rd(x);
  rd(y);
}
template <class T, class S, class U>
inline void rd(T *x, S *y, U *z) {
  rd(x);
  rd(y);
  rd(z);
}
template <class T, class S, class U, class V>
inline void rd(T *x, S *y, U *z, V *w) {
  rd(x);
  rd(y);
  rd(z);
  rd(w);
}
inline void wr(int x) {
  if (x < 10)
    putchar('0' + x);
  else
    wr(x / 10), wr(x % 10);
}
inline void wr(int x, char c) {
  int s = 0, m = 0;
  char f[10];
  if (x < 0) m = 1, x = -x;
  while (x) f[s++] = x % 10, x /= 10;
  if (!s) f[s++] = 0;
  if (m) putchar('-');
  while (s--) putchar(f[s] + '0');
  putchar(c);
}
inline void wr(long long x, char c) {
  int s = 0, m = 0;
  char f[20];
  if (x < 0) m = 1, x = -x;
  while (x) f[s++] = x % 10, x /= 10;
  if (!s) f[s++] = 0;
  if (m) putchar('-');
  while (s--) putchar(f[s] + '0');
  putchar(c);
}
inline void wr(double x, char c) {
  printf("%.15f", x);
  putchar(c);
}
inline void wr(const char c[]) {
  int i;
  for (i = 0; c[i] != '\0'; i++) putchar(c[i]);
}
inline void wr(const char x[], char c) {
  int i;
  for (i = 0; x[i] != '\0'; i++) putchar(x[i]);
  putchar(c);
}
template <class T>
inline void wrn(T x) {
  wr(x, '\n');
}
template <class T, class S>
inline void wrn(T x, S y) {
  wr(x, ' ');
  wr(y, '\n');
}
template <class T, class S, class U>
inline void wrn(T x, S y, U z) {
  wr(x, ' ');
  wr(y, ' ');
  wr(z, '\n');
}
template <class T, class S, class U, class H>
inline void wrn(T x, S y, U z, H h) {
  wr(x, ' ');
  wr(y, ' ');
  wr(z, ' ');
  wr(h, '\n');
}
template <class T>
inline void wra(T x[], int n) {
  int i;
  if (!n) {
    putchar('\n');
    return;
  }
  for (register int i = (0); i < (n - 1); ++i) wr(x[i], ' ');
  wr(x[n - 1], '\n');
}
int a[maxn], cnt[maxn][maxn];
int main() {
  int t;
  rd(&t);
  while (t--) {
    int n;
    rd(&n);
    rd(a + 1, n);
    for (register int i = (1); i < (n + 1); ++i) {
      for (register int j = (1); j < (n + 1); ++j) cnt[i][j] = cnt[i - 1][j];
      cnt[i][a[i]]++;
    }
    long long ans = 0, as = 0;
    for (register int i = (1); i < (n + 1); ++i) {
      as = 0;
      for (register int j = (i + 1); j < (n); ++j) {
        as += 1ll * (cnt[j][a[j]] - cnt[i][a[j]]) *
                  (cnt[n][a[j]] - cnt[j][a[j]]) -
              1ll * (cnt[j - 1][a[j]] - cnt[i][a[j]]) *
                  (cnt[n][a[j]] - cnt[j - 1][a[j]]);
        if (a[i] != a[j + 1]) continue;
        ans += as - (cnt[j][a[j + 1]] - cnt[i][a[j + 1]]);
      }
    }
    wrn(ans);
  }
}

```