一天，williamchenwl88在给他优秀的徒弟Glory讲解LCA（最近公共祖先）。因为Glory太优秀了所以一下就学会了，谁知williamchenwl88却说“你还是太菜了”，然后丢给了Glory一道题。虽然对Glory来说这是一道非常简单的题，但是比起向williamchenwl88证明自己不菜还是把妹更重要，于是忙着把妹的Glory就把这道题丢给了没有妹子的你。

给你一棵有根树，根节点的编号为1，每个节点有一个权值A[i]，问有多少无序点对(u, v)满足u != v且A[u]*A[v]=A[lca(u, v)]

第一行一个数字T表示数据组数。

每组数据的第一行是一个整数n(n<=30000)表示节点个数。

接下来n-1行，每行两个数字u，v表示树上有一条边(u, v)

接下来一行n个数字表示A[1] ……A[n]。（A[i]<=10^9）

每组数据输出一个数字表示答案。

shijieyywd