You are a CEO of a group of companies ($N$ companies form a rooted tree structure), and the country you live in has a weird tax system. Suppose if a company makes $X$ rs profit then it has to pay $Y$ rs tax, here the $Y$ is the number of prime factors of $X$.Calculate the total tax paid by all the companies in the group. Company 1 is the parent of all companies.

Tax paid by a company is equal to the tax paid by its direct children and the tax paid on the profits earned by that company.

Input : 

The first line contains $T$, the number of test cases ($1 \leq T \leq 10^3$)
The first line of each test case contains $N$, the number of companies ($1 \leq N \leq 10^5$)
The second line of each test case contains an array profit $a_1,a_2,a_3,....a_n$ ($1 \leq a_i \leq 10^6$)
The next $(N-1)$ lines contain two numbers $u,v$. There is an edge between $u$ and $v$
The structure is guaranteed to be a tree.

It is guaranteed that the sum of $N$ over all test cases doesn't exceed $10^5$.

Output:

Print an array of size $N$ ,where $A_i$ is the amount of tax paid by the company $i$