Cho một cây gồm ~N~ nút đánh số từ ~1 \rightarrow N~. Các cạnh của cây đánh số từ ~1 \rightarrow N-1~, mỗi cạnh có trọng số là một số nguyên. Bạn cần viết chương trình thực hiện dãy các lệnh sau:

• CHANGE ~i~ ~v~ ~\rightarrow~ Thay đổi trọng số của cạnh thứ ~i~ thành ~v~
• NEGATE ~a~ ~b~ ~\rightarrow~ Đảo dấu trọng số của tất cả các cạnh nằm trên đường đi từ ~a~ đến ~b~
• QUERY ~a~ ~b~ ~\rightarrow~ Tìm trọng số lớn nhất của các cạnh nằm trên đường đi từ ~a~ đến ~b~

Input

Input là một bộ gồm nhiều test. Dòng đầu của input là số test ~t~ ~(t \leq 20)~. Tiếp sau đó là các test.

• Mỗi test bắt đầu bằng một dòng trống. Dòng tiếp theo ghi một số ~N~ ~(N \leq 10000)~. ~N-1~ dòng tiếp theo, mỗi dòng ghi ~3~ số ~a~, ~b~ và ~c~ mô tả một cạnh của cây nối ~a~ với ~b~ và có trọng số là ~c~. Thứ tự của các cạnh chính là thứ tự xuất hiện trong input. Tiếp theo là dãy các lệnh như mô tả ở trên(số lệnh không quá ~50000)~. Cuối mỗi test ghi một từ "DONE".
• Dữ liệu vào luôn đảm bảo trọng số của các cạnh ở mỗi thời điểm có giá trị tuyệt đối không vượt quá ~10\,000\,000~.

Output

• Với mỗi lệnh "QUERY", in ra kết quả tìm được. Nếu ~a = b~ thì ghi ra ~0~.

Sample Input

1

3
1 2 1
2 3 2
QUERY 1 2
CHANGE 1 3
QUERY 1 2
DONE

Sample Output

1
3