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\)