#include <bits/stdc++.h>
using namespace std;
template <typename T1, typename T2>
string print_iterable(T1 begin_iter, T2 end_iter, int counter) {
  bool done_something = false;
  stringstream res;
  res << "[";
  for (; begin_iter != end_iter and counter; ++begin_iter) {
    done_something = true;
    counter--;
    res << *begin_iter << ", ";
  }
  string str = res.str();
  if (done_something) {
    str.pop_back();
    str.pop_back();
  }
  str += "]";
  return str;
}
vector<int> SortIndex(int size, std::function<bool(int, int)> compare) {
  vector<int> ord(size);
  for (int i = 0; i < size; i++) ord[i] = i;
  sort(ord.begin(), ord.end(), compare);
  return ord;
}
template <typename T>
bool MinPlace(T& a, const T& b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template <typename T>
bool MaxPlace(T& a, const T& b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <typename S, typename T>
ostream& operator<<(ostream& out, const pair<S, T>& p) {
  out << "{" << p.first << ", " << p.second << "}";
  return out;
}
template <typename T>
ostream& operator<<(ostream& out, const vector<T>& v) {
  out << "[";
  for (int i = 0; i < (int)v.size(); i++) {
    out << v[i];
    if (i != (int)v.size() - 1) out << ", ";
  }
  out << "]";
  return out;
}
template <class TH>
void _dbg(const char* name, TH val) {
  clog << name << ": " << val << endl;
}
template <class TH, class... TA>
void _dbg(const char* names, TH curr_val, TA... vals) {
  while (*names != ',') clog << *names++;
  clog << ": " << curr_val << ", ";
  _dbg(names + 1, vals...);
}
const int MAXN = 3010;
vector<int> pos[MAXN];
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int T;
  cin >> T;
  for (int t = 1; t <= T; t++) {
    int N;
    cin >> N;
    for (int i = 1; i <= N; i++) pos[i].clear();
    vector<int> A(N);
    for (int i = 0; i < N; i++) cin >> A[i], pos[A[i]].push_back(i);
    long long res = 0;
    for (int i = 1; i <= N; i++)
      for (int j = 1; j <= N; j++) {
        if (pos[i].size() <= 1 or pos[j].size() <= 1) continue;
        vector<int> op;
        vector<int> cl;
        for (int x : pos[i])
          for (int y : pos[j]) {
            if (x < y) op.push_back(x), cl.push_back(y);
          }
        sort(op.begin(), op.end());
        sort(cl.begin(), cl.end());
        int it0 = 0;
        int it1 = 0;
        long long cnt = 0;
        while (it1 < ((int)((cl).size()))) {
          if (it0 < ((int)((op).size())) and op[it0] <= cl[it1]) {
            res += cnt;
            it0++;
          } else {
            cnt++;
            it1++;
          }
        }
      }
    cout << res << "\n";
  }
}

### Prompt

Your task is to create 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;
template <typename T1, typename T2>
string print_iterable(T1 begin_iter, T2 end_iter, int counter) {
  bool done_something = false;
  stringstream res;
  res << "[";
  for (; begin_iter != end_iter and counter; ++begin_iter) {
    done_something = true;
    counter--;
    res << *begin_iter << ", ";
  }
  string str = res.str();
  if (done_something) {
    str.pop_back();
    str.pop_back();
  }
  str += "]";
  return str;
}
vector<int> SortIndex(int size, std::function<bool(int, int)> compare) {
  vector<int> ord(size);
  for (int i = 0; i < size; i++) ord[i] = i;
  sort(ord.begin(), ord.end(), compare);
  return ord;
}
template <typename T>
bool MinPlace(T& a, const T& b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template <typename T>
bool MaxPlace(T& a, const T& b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <typename S, typename T>
ostream& operator<<(ostream& out, const pair<S, T>& p) {
  out << "{" << p.first << ", " << p.second << "}";
  return out;
}
template <typename T>
ostream& operator<<(ostream& out, const vector<T>& v) {
  out << "[";
  for (int i = 0; i < (int)v.size(); i++) {
    out << v[i];
    if (i != (int)v.size() - 1) out << ", ";
  }
  out << "]";
  return out;
}
template <class TH>
void _dbg(const char* name, TH val) {
  clog << name << ": " << val << endl;
}
template <class TH, class... TA>
void _dbg(const char* names, TH curr_val, TA... vals) {
  while (*names != ',') clog << *names++;
  clog << ": " << curr_val << ", ";
  _dbg(names + 1, vals...);
}
const int MAXN = 3010;
vector<int> pos[MAXN];
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int T;
  cin >> T;
  for (int t = 1; t <= T; t++) {
    int N;
    cin >> N;
    for (int i = 1; i <= N; i++) pos[i].clear();
    vector<int> A(N);
    for (int i = 0; i < N; i++) cin >> A[i], pos[A[i]].push_back(i);
    long long res = 0;
    for (int i = 1; i <= N; i++)
      for (int j = 1; j <= N; j++) {
        if (pos[i].size() <= 1 or pos[j].size() <= 1) continue;
        vector<int> op;
        vector<int> cl;
        for (int x : pos[i])
          for (int y : pos[j]) {
            if (x < y) op.push_back(x), cl.push_back(y);
          }
        sort(op.begin(), op.end());
        sort(cl.begin(), cl.end());
        int it0 = 0;
        int it1 = 0;
        long long cnt = 0;
        while (it1 < ((int)((cl).size()))) {
          if (it0 < ((int)((op).size())) and op[it0] <= cl[it1]) {
            res += cnt;
            it0++;
          } else {
            cnt++;
            it1++;
          }
        }
      }
    cout << res << "\n";
  }
}

```