Đề gốc được viết bằng thơ, dựa trên The Lorax. Bạn đọc hứng thú có thể xem bài gốc trên Codeforces. Dưới đây là tóm tắt của đề bài.

Tôi là Lorax, tôi nói cho Cây!

Thần rừng Lorax muốn nhờ bạn trồng cây trong thành phố Thneedville. Thành phố được mô tả bằng một đồ thị liên thông gồm ~n~ đỉnh và ~n-1~ cạnh. Bạn phải giúp thần Lorax tổng cộng ~q~ lần, mỗi lần đặt ~x_i~ hạt giống và ~x_i~ chậu cây tại hai đỉnh khác nhau ~a_i~ và ~b_i~. Tuy nhiên nếu ~x_i = 0~, bạn sẽ phải trả lời câu hỏi sau:

Nếu hiện giờ bạn phải nối mỗi hạt giống với mỗi chậu cây trong thành phố sao cho tổng khoảng cách giữa mỗi cặp là nhỏ nhất có thể, có bao nhiêu cặp sẽ đi qua cạnh nối giữa ~a_i~ và ~b_i~?

Input

Dòng đầu tiên chứa số nguyên ~c~ ~(1 \le c \le 20)~ là số lượng test. Mỗi test gồm:

• Với mỗi test, dòng đầu tiên chứa hai số nguyên ~n~ và ~q~ ~(1 \le n, q \le 10^5)~ lần lượt là số đỉnh trong Thneedville và số lần bạn cần giúp thần Lorax.

• ~n-1~ dòng tiếp theo mô tả các cạnh trong Thneedville. Dòng thứ ~i~ chứa hai số nguyên ~u_i~, ~v_i~ ~(1 \le u_i, v_i \le n,\ u_i \neq v_i)~ thể hiện có cạnh nối giữa đỉnh ~u_i~ và ~v_i~.

• ~q~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~a_i~, ~b_i~, ~x_i~ ~(1 \le a_i, b_i \le n,\ a_i \neq b_i,\ 0 \le x \le 10^8)~. Nếu ~x_i=0~, bạn cần in ra số lượng cặp hạt giống - chậu cây đi qua cạnh nối giữa ~a_i~ và ~b_i~ (đảm bảo sẽ có cạnh nối trực tiếp giữa ~a_i~ và ~b_i~). Nếu ~x_i>0~, bạn cần đặt ~x_i~ hạt giống tại đỉnh ~a_i~ và ~x_i~ chậu cây tại đỉnh ~b_i~.

Output

Với mỗi câu hỏi có ~x_i=0~, in ra một số nguyên duy nhất là số lượng cặp hạt giống - chậu cây đi qua cạnh nối giữa ~a_i~ và ~b_i~.

Sample Input

2
6 5
1 2
2 3
3 4
4 5
4 6
1 6 2
2 5 3
4 3 0
6 2 2
4 3 0
4 6
1 2
1 3
4 1
1 2 0
3 4 5
4 2 1
1 3 0
1 4 0
1 2 0

Sample Output

5
3
0
5
4
1