"Giữa lòng cuộc chiến tranh khốc liệt, nơi bom đạn và gian khổ không ngừng thử thách ý chí con người, tinh thần quật cường và trí tuệ sáng tạo của quân và dân Việt Nam, đặc biệt là các chiến sĩ du kích, đã tỏa sáng rực rỡ. Một trong những biểu tượng tiêu biểu cho sự kiên cường và bí mật chiến đấu là hệ thống địa đạo Củ Chi, những "con đường thép" ẩn mình sâu dưới lòng đất. Đây không chỉ là nơi trú ẩn an toàn trước hỏa lực dày đặc của kẻ thù, mà còn là mạng lưới giao thông, liên lạc bí mật, kết nối các căn cứ địa và chiến lược, giúp vận chuyển lực lượng, vũ khí và mệnh lệnh một cách kín đáo. Địa đạo Củ Chi, cùng với các chiến công khác, góp phần quan trọng vào thành công của những chiến dịch lớn, đặc biệt là Chiến dịch Hồ Chí Minh năm 1975, dẫn đến thắng lợi vĩ đại vào ngày 30/4, giải phóng miền Nam, thống nhất đất nước."

Trong những ngày tháng hào hùng của chiến dịch Hồ Chí Minh, hệ thống địa đạo đóng vai trò huyết mạch trong việc đảm bảo liên lạc thông suốt và bí mật giữa các đơn vị cách mạng. Hãy hình dung mạng lưới địa đạo như một đồ thị cây ~G~ khổng lồ, bao gồm ~N~ hầm chỉ huy then chốt (các đỉnh của đồ thị), đóng vai trò là trung tâm điều phối thông tin, và ~N-1~ đoạn địa đạo kết nối trực tiếp giữa các hầm này (tương ứng với các cạnh của đồ thị). Cấu trúc cây đảm bảo rằng luôn tồn tại một tuyến liên lạc duy nhất và không bị trùng lặp giữa hai hầm chỉ huy bất kỳ, yếu tố sống còn để tránh bị lộ thông tin và đảm bảo mệnh lệnh được truyền đạt chính xác.

Trong mô hình này, mỗi đoạn địa đạo nối hai hầm chỉ huy ~u~ và ~v~ có một thuộc tính quan trọng, thể hiện "Độ rõ Tín hiệu Liên lạc" ~(D)~. Ban đầu, do điều kiện xây dựng khác nhau, chiều dài, độ sâu, và các biện pháp bảo vệ khác nhau, độ rõ tín hiệu này có thể không đồng đều giữa các đoạn địa đạo. Độ rõ tín hiệu càng thấp đồng nghĩa với việc thông tin truyền đi càng khó khăn, dễ bị nhiễu hoặc mất mát, ảnh hưởng đến sự phối hợp tác chiến.

Bộ Chỉ huy nhận được ~Q~ yêu cầu "Kiểm tra Đường dây Nóng", mỗi yêu cầu là một cặp hầm chỉ huy ~(u, v)~.

Nhiệm vụ:

• Xác định số biện pháp kỹ thuật tối thiểu cần thực hiện trên đường đi duy nhất từ hầm ~u~ đến hầm ~v~ để Chuẩn hóa Độ rõ Tín hiệu trên tuyến liên lạc này.

• Chuẩn hóa Độ rõ Tín hiệu trên tuyến liên lạc nghĩa là điều chỉnh độ rõ tín hiệu của một số đoạn địa đạo trên tuyến sao cho tất cả các đoạn đều có cùng một giá trị độ rõ tín hiệu.

• Mỗi biện pháp kỹ thuật là việc chọn một đoạn địa đạo trên tuyến và thay đổi độ rõ tín hiệu của nó thành bất kỳ mức nào mong muốn.

• Lưu ý rằng: Sau mỗi nhiệm vụ, trạng thái mạng địa đạo trở về ban đầu, bởi vì trong thực tế, các phương án cải thiện tín hiệu chỉ được lên kế hoạch và giả lập, chưa thực hiện ngay lập tức để bảo mật và đảm bảo an toàn cho toàn chiến dịch.

Hãy lập trình để tìm ra con số tối thiểu này cho mỗi truy vấn, thể hiện khả năng đảm bảo thông tin liên lạc thông suốt và hiệu quả, góp phần vào thắng lợi cuối cùng của chiến dịch Hồ Chí Minh trong địa đạo mô phỏng này.

Input Format

• Dòng đầu tiên: Một số nguyên ~N~ ~(1 \le N \le 10^5 )~ — số lượng hầm chỉ huy.
• ~N-1~ dòng tiếp theo: Mỗi dòng gồm 3 số nguyên ~u~, ~v~, ~D~ ~(1 \le u,v \le n , u \neq v , D \le 26)~ — mô tả đoạn địa đạo nối ~u~ và ~v~ với độ rõ tín hiệu ~D~.
• Dòng tiếp theo: Một số nguyên ~Q~ ~(1 \le Q \le 10^5)~ — số lượng yêu cầu kiểm tra.
• ~Q~ dòng tiếp theo: Mỗi dòng gồm hai số nguyên ~u~, ~v~ — yêu cầu kiểm tra tuyến liên lạc từ ~u~ đến ~v~.

Output Format

• Gồm ~Q~ dòng, mỗi dòng là số biện pháp kỹ thuật tối thiểu cần thực hiện cho yêu cầu tương ứng.

Subtask

• Subtask 1: Có ~20\%~ số điểm có ~1 \leq N, Q \leq 500~
• Subtask 2: ~30\%~ số điểm có ~1 \leq N, Q \leq 5 \times 10^3~
• Subtask 3: ~50\%~ số điểm còn lại không có giới hạn gì thêm

Sample Input

8
1 2 6
1 3 4
3 6 6 
3 8 8
8 7 2
2 5 3
2 4 6
4
4 6
8 4
6 5
7 4

Sample Output

1
2
2
3

Giải thích

• Ở truy vấn đầu tiên, ta thay đổi trọng số của cạnh ~[1,3]~ thành ~6~. Sau thao tác này, tất cả các cạnh trên đường đi từ ~4~ đến ~6~ đều có trọng số bằng ~6~. Do đó, đáp án là ~1~.

• Ở truy vấn thứ hai, ta thay đổi trọng số của các cạnh ~[8,3]~ và ~[3,1]~ thành ~6~. Sau các thao tác này, tất cả các cạnh trên đường đi từ ~8~ đến ~4~ đều có trọng số bằng ~6~. Do đó, đáp án là ~2~.

• Ở truy vấn thứ ba, ta thay đổi trọng số của các cạnh ~[1,3]~ và ~[5,2]~ thành ~6~. Sau các thao tác này, tất cả các cạnh trên đường đi từ ~6~ đến ~5~ đều có trọng số bằng ~6~. Do đó, đáp án là ~2~.

• Ở truy vấn thứ tư, ta thay đổi trọng số của các cạnh ~[8,7]~, ~[8,3]~ và ~[1,3]~ thành ~6~. Sau các thao tác này, tất cả các cạnh trên đường đi từ ~7~ đến ~4~ đều có trọng số bằng ~6~. Do đó, đáp án là ~3~.