Play with Trees

In Amber's childhood, he usually liked to observe some little things for tickling his little curiosity. He often found it interesting to climb up a tree, sit on a branch and watch the movement of a group of lovely ants on the branches of the tree.

Amber finds there are n ant holes and m ants in the tree now. Because of his careful observation, he knows all ants' behaviors, the i-th ant wanna travel from one hole s_i to another hole t_i at the speed v_i.

During the ant's travel, if two ants arrive at the same position (meet or chase), they will touch their feelers for exchanging the information about food or danger. Even at the moment that the travel starts or finishes, the ant can also touch other's feelers. But after the travel finishes, the ant will enter into the hole and never touch feelers. What amber wonders is to count the times of touchings during the whole traveling process.

Consider there are n - 1 branches in the tree. Each branch connects the adjacent ant holes and has a particular length. Assume there is always a path that consists of branches between any two ant holes. Assume that no two ants have the same speeds and the touching doesn't cost any time.

Input

Input consists of multiple testcases. The first line contains one integer t (1 <= t <= 20). For each testcase, the input format is following.

The first line contains one integer n (1 <= n <= 10⁶). In next n - 1 line, the i-th line contains an integer triple (u_i, v_i, w_i) (1 <= u_i, v_i <= n, u_i != v_i, 1 <= w_i <= 10³). The triple means there is a branch with the length w_i between node u_i and node v_i.

The next line contains one integer m (1 <= m <= 10³). In next m line, the i-th line contains an integer triple (s_i, t_i, v_i) (1 <= s_i, t_i <= n, 1 <= v_i <= 10⁶). The triple means that the i-th ant's travel is from s_i to t_i at the speed v_i.

Output

For each testcase, print a line that consists of an integer that means the times of the feeler touchings.

Example

Input:
1
3
1 2 1
2 3 1
3
1 3 1
3 1 1
1 2 3

Output:
2

Note: It's a partly correct problem, so score is set for each case. When you pass all cases, you'll get 300 points