#include <iostream>
#include <algorithm>
#include <assert.h>
#include <map>
#include <vector>
using namespace std;

long long readInt(long long l,long long r,char endd){
	long long x=0;
	int cnt=0;
	int fi=-1;
	bool is_neg=false;
	while(true){
		char g=getchar();
		if(g=='-'){
			assert(fi==-1);
			is_neg=true;
			continue;
		}
		if('0'<=g && g<='9'){
			x*=10;
			x+=g-'0';
			if(cnt==0){
				fi=g-'0';
			}
			cnt++;
			assert(fi!=0 || cnt==1);
			assert(fi!=0 || is_neg==false);
			
			assert(!(cnt>19 || ( cnt==19 && fi>1) ));
		} else if(g==endd){
			if(is_neg){
				x= -x;
			}
			assert(l<=x && x<=r);
			return x;
		} else {
			assert(false);
		}
	}
}
string readString(int l,int r,char endd){
	string ret="";
	int cnt=0;
	while(true){
		char g=getchar();
		assert(g!=-1);
		if(g==endd){
			break;
		}
		cnt++;
		ret+=g;
	}
	assert(l<=cnt && cnt<=r);
	return ret;
}
long long readIntSp(long long l,long long r){
	return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
	return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
	return readString(l,r,'\n');
}
string readStringSp(int l,int r){
	return readString(l,r,' ');
}





vector<int> adj[100100];

vector<pair<int,int> > factor[100100];

int T;
int n;

bool vv[100100];
bool ok;
void is_tree(int nd,int p){
	vv[nd]=true;
	for(int i=0;i<adj[nd].size();i++){
		int ch=adj[nd][i];
		if(ch==p)continue;
		if(vv[ch]){
			ok=false;
			break;
		}
		is_tree(ch,nd);
	}
}


long long p3[1001001];
long long p32[1001001];

long long mod=1000000007;
long long mod2=1000000009;

int rep[1001001];
int ver[1001001];
int vern=0;

long long hsh;
long long hsh2;
int get_val(int ind){
	if(ver[ind]==vern){
		return rep[ind];
	}
	return 0;
}
void update(int ind,int val){
	rep[ind]=val;
	ver[ind]=vern;
}

bool is_del[1001001];
int sum[100100];

void dfs_sum(int nd,int p){
	sum[nd]=1;
	for(int i=0;i<adj[nd].size();i++){
		int ch=adj[nd][i];
		if(ch==p)continue;
		if(is_del[ch])continue;
		dfs_sum(ch,nd);
		sum[nd]+= sum[ch];
	}
}

int find_cen(int nd,int p,int s){
	for(int i=0;i<adj[nd].size();i++){
		int ch=adj[nd][i];
		if(ch==p)continue;
		if(is_del[ch])continue;
		if(sum[ch] * 2 > s){
			return find_cen(ch,nd,s);
		}
	}
	return nd;
}

int sol=0;


map<pair<int,int>,int> store;

void _add(int ind){
	int s=factor[ind].size();
	for(int i=0;i<s;i++){
		int rp=factor[ind][i].second;
		int g=factor[ind][i].first;

		int vl= get_val(g);
		hsh -= vl * p3[g];
		hsh2 -= vl * p32[g];
		
		vl += rp;
		vl %=3;

		hsh += vl * p3[g];
		hsh2 += vl * p32[g];

		update(g,vl);
	}
	hsh %= mod;
	if(hsh<0)hsh+=mod;
	hsh2 %= mod2;
	if(hsh2<0)hsh2+=mod2;
}

void _sub(int ind){
	int s=factor[ind].size();
	for(int i=0;i<s;i++){
		int rp=factor[ind][i].second;
		int g=factor[ind][i].first;

		int vl= get_val(g);
		hsh -= vl * p3[g];
		hsh2 -= vl * p32[g];
		
		vl += 3- rp;
		vl %=3;

		hsh += vl * p3[g];
		hsh2 += vl * p32[g];
		
		update(g,vl);
	}
	hsh %= mod;
	if(hsh<0)hsh+=mod;
	hsh2 %= mod2;
	if(hsh2<0)hsh2+=mod2;
}

void dfs_add(int nd,int p,int dist){
	_add(nd);
	store[make_pair(hsh,hsh2)] = max(store[make_pair(hsh,hsh2)],dist);
	for(int i=0;i<adj[nd].size();i++){
		int ch=adj[nd][i];
		if(ch==p)continue;
		if(is_del[ch])continue;

		dfs_add(ch,nd,dist+1);
	}
	_sub(nd);
}

void dfs_cal(int nd,int p,int dist){
	_sub(nd);
	if(store.count(make_pair(hsh,hsh2))){
		sol = max( sol,store[make_pair(hsh,hsh2)] + dist);
	}
	

	for(int i=0;i<adj[nd].size();i++){
		int ch=adj[nd][i];
		if(ch==p)continue;
		if(is_del[ch])continue;

		dfs_cal(ch,nd,dist+1);
	}
	_add(nd);
}

void divide(int nd){
	dfs_sum(nd,nd);
	nd = find_cen(nd,nd,sum[nd]);
	store.clear();
	store[make_pair(0,0)]=0;
	for(int i=0;i<adj[nd].size();i++){
		int ch=adj[nd][i];
		if(is_del[ch])continue;
		vern++;
		hsh=0;
		hsh2=0;
		_sub(nd);
		if(store.count(make_pair(hsh,hsh2))){
			sol = max( sol,store[make_pair(hsh,hsh2)] + 1);
		}
		
		dfs_cal(ch,nd,2);

		vern++;
		hsh=0;
		hsh2=0;
		dfs_add(ch,nd,1);
	}

	is_del[nd]=true;
	for(int i=0;i<adj[nd].size();i++){
		int ch=adj[nd][i];
		if(is_del[ch])continue;
		divide(ch);
	}

}

int main(){
	//cin>>T;
	T=readIntLn(1,5000);

	p3[0]=1;
	p32[0]=1;
	for(int i=1;i<=1000000;i++){
		p3[i] = (p3[i-1]*3)%mod;
		p32[i] = (p32[i-1]*3)%mod2;
	}
	while(T--){
		//cin>>n;
		ok=true;
		n=readIntLn(1,100000);
		sol=-1;
		for(int i=1;i<=n;i++){
			vv[i]=false;
			is_del[i]=false;
			adj[i].clear();
			factor[i].clear();
		}
		for(int j=1;j<=n;j++){
			int x;
			if(j==n){
				x=readIntLn(1,1000000);
			} else {
				x=readIntSp(1,1000000);
			}
			for(int i=2;i*i<=x;i++){
				if(x%i==0){
					int rp=0;
					while(x%i==0){
						x/=i;
						rp++;
					}
					if(rp%3)
						factor[j].push_back(make_pair(i,rp%3));
				}
			}
			if(x>1){
				factor[j].push_back(make_pair(x,1));
			}
			if(factor[j].size() == 0){
				sol =max(sol,1);
			}
		}
		for(int i=1;i<n;i++){
			int a,b;
			//cib>>a>>b;
			a=readIntSp(1,n);
			b=readIntLn(1,n);
			adj[a].push_back(b);
			adj[b].push_back(a);
		}
		is_tree(1,1);
		for(int i=1;i<=n;i++){
			assert(vv[i]);
		}
		assert(ok);
		divide(1);
		cout<<sol<<endl;
	}
	assert(getchar()==-1);
}