Fiber-optic Network

Time Limit: 15 Seconds

Memory Limit: 262144 KB

Description

Marjar University has decided to upgrade the infrastructure of school intranet by using fiber-optic technology. There are N buildings in the school. Each building will be installed with one router. These routers are connected by optical cables in such a way that there is exactly one path between any two routers.

Each router should be initialized with an operating frequency Fi before it starts to work. Due to the limitations of hardware and environment, the operating frequency should be an integer number within [Li, Ri]. In order to reduce the signal noise, the operating frequency of any two adjacent routers should be co-prime.

Edward is the headmaster of Marjar University. He is very interested in the number of different ways to initialize the operating frequency. Please write a program to help him! To make the report simple and neat, you only need to calculate the sum of Fi (modulo 1000000007) in all solutions for each router.

Input

There are multiple test cases. The first line of input contains an integer T indicating the number of test cases. For each test case:

The first line contains one integer N (1 <= N <= 50). The next line contains N integers Li (1 <= Li <= 50000). Then, the following line contains N integers Ri (Li <= Ri <= 50000).

For the next N - 1 lines, each line contains two integers Xi and Yi. That means there is an optical cable connecting router Xi and router Yi (indexes are 1-based).

Output

For each test case, output a line with N integers representing the sum of Fi (modulo 1000000007) in all solutions.

Sample Input

2
4
1 2 3 4
2 3 4 5
1 2
2 3
3 4
4
1 2 3 4
2 3 4 5
1 2
1 3
1 4


Sample Output

5 10 14 19
10 23 31 41


Hint

In the first sample test case, there are 4 ways to initialize the operating frequency:

• 1 2 3 4
• 1 2 3 5
• 1 3 4 5
• 2 3 4 5

None