Description

一棵树的节点编号为$1$～$N$ ，边的编号为$1$$～$$N$ $-$$1$，每条边都带有权值。在树上执行一系列指令，形式如下。

Format

Input

输入包含多个测试用例。第$1$行为测试用例的数量$T$ $（$$T$$≤$$2$$0$$）$。每个测试用例的前面都有一个空行。第$1$个非空行包含$N$ $（$$N$$≤$$1$$0$,$0$$0$$0$$）$。接下来的$N$ -$1$行，每行都包含$3$个整数$a$ 、$b$ 和$c$ ，表示边的两个节点$a$ 和$b$ 及该边的权值$c$ 。边按输入的顺序编号。若在行中出现单词“$D$$O$$N$$E$”，则标志着结束。

Output

对每条$Q$$U$$E$$R$$Y$指令，都单行输出结果。

Samples

1

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

1
3