/******************************************
*    AUTHOR:         BHUVNESH JAIN        *
*    INSTITUITION:   BITS PILANI, PILANI  *
******************************************/
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef long double LD;
typedef pair<int,int> pii;
typedef pair<LL, LL> pll;

#define fi				first
#define sec 			second
#define inchar          getchar_unlocked
#define outchar(x)      putchar_unlocked(x)

template<typename T> void inpos(T &x) {
	x = 0; register T c = inchar();
	while(((c < 48) || (c > 57)) && (c != '-')) c = inchar();
	for(; c < 48 || c > 57; c = inchar()) ;
	for(; c > 47 && c < 58; c = inchar()) x = (x<<3) + (x<<1) + (c&15);
}

template<typename T> void outpos(T n) {
	if(n < 0) { outchar('-'); n *= -1; }
	char snum[65]; int i = 0;
	do {
		snum[i++] = n % 10 + '0';
		n /= 10;
	} while(n);
	i = i - 1;
	while (i >= 0) outchar(snum[i--]); outchar('\n');
}


const int MAX = 1000001;

int ans;
int dis[MAX];
int cube[MAX];
vector<int> adj[MAX];
vector<pii> fac[MAX];
vector<int> lp, primes;

void factor_sieve() {
	lp.resize(MAX);
	lp[1] = 1;
	for (int i = 2; i < MAX; ++i) {
		if (lp[i] == 0) {
			lp[i] = i;
			primes.emplace_back(i);
		}
		for (int j = 0; j < primes.size() && primes[j] <= lp[i]; ++j) {
			int x = i * primes[j];
			if (x >= MAX) break;
			lp[x] = primes[j];
		}
	}
}

int reduce(int x) {
	int ans = x;
	for(int i = 2; i <= 100; ++i) {
		int y = i * i * i;
		if (y > ans) {
			break;
		}
		while(ans%y == 0) {
			ans /= y;
		}
	}
	return ans;
}

vector<pii> factorise(int x) {
	vector<pii> ans;
	while(x != 1) {
		int p = lp[x], e = 0;
		while(x % p == 0) x /= p, e += 1;
		assert(e < 3);
		ans.push_back({p, e});
	}
	return ans;
}

void dfs(int u, int p, int d, int bad) {
	for(auto it : fac[u]) {
		if (cube[it.fi]%3 != 0) {
			cube[it.fi] += it.sec;
			if (cube[it.fi]%3 == 0) {
				bad -= 1;
			}
		}
		else {
			cube[it.fi] += it.sec;
			if (cube[it.fi]%3 != 0) {
				bad += 1;
			}
		}
	}
	if (bad == 0) {
		ans = max(ans, d);
	}
	for(auto v : adj[u]) {
		if (v != p) {
			dfs(v, u, d+1, bad);
		}
	}
	for(auto it : fac[u]) {
		if (cube[it.fi]%3 != 0) {
			cube[it.fi] -= it.sec;
			if (cube[it.fi]%3 == 0) {
				bad -= 1;
			}
		}
		else {
			cube[it.fi] -= it.sec;
			if (cube[it.fi]%3 != 0) {
				bad += 1;
			}
		}
	}
}

int main() {
	#ifndef ONLINE_JUDGE
		freopen("inp2.txt", "r", stdin);
	#endif
	factor_sieve();
	int t, n, x, y;
	inpos(t);
	while(t--) {
		inpos(n);
		for(int i = 1; i <= n; ++i) {
			inpos(x);
			fac[i] = factorise(reduce(x));
			adj[i].clear();
		}
		for(int i = 1; i < n; ++i) {
			inpos(x), inpos(y);
			adj[x].push_back(y);
			adj[y].push_back(x);
		}
		ans = -1;
		for(int i = 1; i <= n; ++i) {
			dfs(i, 0, 1, 0);
		}
		outpos(ans);
	}
	return 0;
}