比较好的题目，别的不说，G1 对 G2 有着不错的启发性。
首先，因为 \(b>0,a_k\le 10^9\)，所以 \(b\) 不可能超过 \(\sqrt{a}\)
考虑对 \(b\) 分类讨论，设置一个阈值 \(B\)，先处理 \(b=1\) 的情况，其实就是取三个相同的数然后排列，可以比较简单的排序之后做到 \(O(n)\)。
接着手写一个哈希表用来存所有 \(a_i\) 出现次数。
然后考虑 \(1\lt b\le B\)，这种情况下我们可以遍历枚举 \(i\)，然后在哈希表中查询 \(ba_i\) 和 \(b^2a_i\) 出现的次数乘起来，注意不要乘上 \(a_i\) 出现的次数，因为每个 \(a_i\) 都会贡献一次。
然后分析 \(b\gt B\) 的情况，我们发现这时候因为 \(a_k\le 10^9\)，所以 \(a_j\le 10^9/B\)，那么我们就先枚举 \(a_j\)，然后对于满足条件的 \(a_j\) 枚举因子作为 \(b\)，一共有大约 \(\sqrt{10^9/B}\) 个。对于其所有大于 \(b\) 的因子，都尝试将其作为 \(b\)，找到 \(a_i/b\) 和 \(ba_i\) 的出现次数乘起来即可。
记 \(B\) 为对 \(b\) 分治的长度，复杂度为 \(O(nB+n\sqrt{\dfrac{a_{max}}{B}})\)
此时取 \(B=a_{max}^{1/3}=1000\) 最优，足以通过此题。
const int N=200005,A=1000000000,B=1000;
ll n,a[200005];
struct hash_table{
#define S 19198100
vector<int>used;
int sz=0,hd[S+5],id[N],nxt[N],w[N];
inline void ins(int k){
int u=k%S;
for(int i=hd[u];i;i=nxt[i])if(id[i]==k)return (void)(w[i]++);
++sz,nxt[sz]=hd[u],w[sz]=1,id[sz]=k,hd[u]=sz;
used.push_back(u);
}
inline int qry(int k){
for (int i=hd[k%S];i;i=nxt[i])if(id[i]==k)return w[i];
return 0;
}
inline void flush(){
sz=0;
for(int i:used)hd[i]=0;
used.clear();
}
}h;
inline void solve(){
cin>>n;
rp(i,n)cin>>a[i];
h.flush();
rp(i,n)h.ins(a[i]);
ll ans=0;
map<ll,ll>mp;
rp(i,n)mp[a[i]]++;
for(auto i:mp)ans+=i.second*(i.second-1)*(i.second-2);
rep(i,2,B){
rp(j,n)if(a[j]*i*i<=A){
ans+=h.qry(a[j]*i)*h.qry(a[j]*i*i);
}
}
rep(i,1,n)if(a[i]<=A/B){
for(ll j=1;j*j<=a[i];j++)if(a[i]%j==0){
if(a[i]*j<=A&&j>B)ans+=h.qry(a[i]/j)*h.qry(a[i]*j);
if(a[i]*(a[i]/j)<=A&&a[i]/j>B)ans+=h.qry(j)*h.qry(a[i]*(a[i]/j));
}
}cout<<ans<<endl;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin>>t;
rd(_,t)solve();
return 0;
}
//Crayan_r