#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int N=3e5+10,base=98773;
int T,n,a[N],sta[N],top,pre[N],f[N];long long ans;
map<ull,int> lst;
ull hs[N];
void init(){
	cin >> n;
	for(int i=1;i<=n;i++) {
        cin >> a[i];
        for(int j = 2; j * j <= a[i]; j++){
            while(a[i] % (j * j) == 0){
                a[i] /= (j * j);
            }
        }
    }
	top=0;ans=0;lst.clear();
}
void work(){
    ans=0;
	for(int i=1;i<=n;i++){
		lst[hs[top]]=i;
		if(top>0&&a[i]==a[sta[top]])top--;
		  else {sta[++top]=i;hs[top]=hs[top-1]*base+a[i];}
		pre[i]=lst[hs[top]];
	}
	for(int i=1;i<=n;i++){
		if(pre[i])f[i]=f[pre[i]-1]+1;
		ans+=f[i];
	}
	cout << ans << endl;
	for(int i=1;i<=n;i++)f[i]=pre[i]=0;
}
int main(){

	//T = 1;
	cin >> T;
	while(T--){
		init();
		work();
	}
}