#include<bits/stdc++.h>
using namespace std;
#define int long long
int n, a[110], ans;
void dfs(int x, int s) {
	if(x == n + 1) {
		int w = sqrt(s);
		if(w * w == s) {
			ans ++;
		}
		return ;
	}
	dfs(x + 1, s);
	dfs(x + 1, s * a[x]);
}
signed main() {
	freopen("square1.in", "r", stdin);
	freopen("square1.out", "w", stdout);
	int t;
	cin >> t;
	for(int tt = 1; tt <= t; tt ++) {
		cin >> n;
		for(int i = 1; i <= n; i ++) {
			cin >> a[i];
		}
		ans = 0;
		dfs(1, 1);
		cout << ans - 1 << endl;
	}
	return 0;
}