Untitled

#include<iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int maxn = 2e6 + 2e4;

int n;
int a[2005];
int f[2001][2001];
int C[maxn];

bool cmp(pair<pair<int, int>, int> &a, pair<pair<int, int>, int> &b){
  if (a.first.first == b.first.first) return a.first.second < b.first.second;
  return a.first.first < b.first.first;
}

void input(){
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> a[i];
  sort(a + 1, a + 1 + n);
  vector<pair<pair<int, int>, int>> g; 
  for (int i = 1; i <= n; i++){
    for (int j = i + 1; j <= n; j++){
      int gcd = __gcd(a[i], a[j]);
      g.push_back({{a[i] / gcd, a[j] / gcd}, i * (n + 1) + j});
    }
  }
  sort(g.begin(), g.end(), cmp);
  int tlast = -1, mlast = -1, cnt = 0;
  for (auto v : g){
    int i = v.second / (n + 1);
    int j = v.second % (n + 1);
    int t = v.first.first;
    int m = v.first.second;
    if (tlast != t || mlast != m){
      ++cnt;
      tlast = t;
      mlast = m;
    }
    f[i][j] = cnt;
    C[f[i][j]]++;
  }
}

void solve(int testcase){
  input();
  long long ans = 0;  
  for (int i = n; i >= 1; i--){
    for (int j = i - 1; j >= 1; j--){
      C[f[j][i]]--;
    }
    for (int j = i + 1; j <= n; j++){
      ans += C[f[i][j]];
    }
  }
  cout << "#" << testcase << ' ' <<  ans << '\n';
}

int main(){
  ios_base::sync_with_stdio(false), cin.tie(0);
  int t = 1;
  cin >> t;
  for (int i = 1; i <= t; i++) solve(i);
}