Là hình mẫu truyền cảm hứng cho bao nhiêu thế hệ đấu sĩ kế cận (xong vẫn vả chúng trên sàn đấu như thường), Piccôlô được vinh danh như một đấu sĩ Huyền Thoại trên đấu trường. Một kỷ niệm chương có hình một cái cây trông hơi giống Piccôlô đã được điêu khắc lên, và sử dụng để vinh danh các đấu sĩ xuất sắc nhất trong các năm tiếp theo.

Ta có thể biểu diễn kỷ niệm chương Piccôlô thành một đồ thị dạng cây gồm ~N~ đỉnh. Trên mỗi đỉnh được gán cho một giá trị ~c_j~, tương ứng với số hiệu của đấu sĩ vô địch giải đấu vào năm thứ ~j~ sau Công Nguyên.

Sau một buổi họp để cải thiện chất lượng tổ chức của các giải đấu cấp dải ngân hà, các hành tinh và bộ tộc đã thống nhất chọn hành tinh chủ nhà cho ~Q~ năm tiếp theo như sau:

• Tính từ năm hiện tại, vào năm thứ ~i~, ta sẽ loại bỏ cạnh ~id_i~ trên "cây kỷ niệm chương Piccôlô" (theo danh sách cạnh cho sẵn.

• Trong hai cây được tạo bởi ~N - 2~ cạnh còn lại, với mỗi cây, ta sẽ đếm xem có bao nhiêu đỉnh có giá trị chia hết cho ~k_i~.

• Số hiệu đại diện cho nước chủ nhà cho giải đấu vào năm thứ ~i~ sẽ là kết quả lớn nhất trong hai số tìm được ở bước trước đó.

Rõ ràng, với một kỷ niệm chương đồ sộ như vậy, thật khó để các nhà tổ chức có thể tự tính toán được bằng tay. Chính vì vậy, bạn hãy giúp họ tính ra danh sách các hành tinh chủ nhà trong những năm tiếp theo nhé!

Input

Dòng đầu chứa ~T~ (~1 \le T \le 1000~) - số test trong một file input. Mỗi test sẽ có format như sau:

• Dòng đầu chứa ~N~ (~1 \le N \le 2 * 10^5~) - số đỉnh trên cây.

• Dòng tiếp theo gồm ~N~ số: ~c_1, c_2, \ldots, c_N~ (~1 \le c_j \le 10^5~). ~c_j~ thể hiện số hiệu được ghi trên đỉnh thứ ~j~ trên cây.

• ~N - 1~ dòng sau, dòng thứ ~i~ chứa hai số nguyên ~u_i, v_i~, thể hiện rằng cạnh thứ ~i~ trong danh sách nối giữa ~u_i~ and ~v_i~.

• Dòng tiếp theo chứa một số ~Q~ (~1 \le Q \le 2 * 10^5~) - số năm bạn phải tính ra hành tinh chủ nhà.

• ~Q~ dòng sau, dòng thứ ~i~ chứa hai số nguyên ~id_i~ và ~k_i~ (~1 \le id_i \le N-1~ và ~1 \le k_i \le 10^5~), thể hiện một truy vấn.

Bộ test đảm bảo rằng dữ liệu đồ thị có dạng cây và tổng ~N~ và ~Q~ không vượt quá ~2 * 10^5~

Output

Mỗi bộ test, in ra ~Q~ dòng, mỗi dòng chứa một số nguyên duy nhất là chỉ số của hành tinh chủ nhà, được tính theo thuật toán đã nêu ra ở đề bài.

Sample Input 1

2
8
1 9 1 12 6 2 3 4
1 2
2 3
1 4
2 5
4 6
5 7
2 8
2
1 2
4 3
7
12 80 36 42 30 8 13
1 2
2 3
2 4
2 6
2 7
1 5
4
2 2
5 13
6 3
2 29

Sample Output 1

2
2
5
1
3
0

Notes

Dưới đây là cây Piccôlô đại diện cho bộ test đầu tiên. Các số ghi trên cạnh là chỉ số tương ứng của cạnh đó theo danh sách cho trước: