Once upon a time there was the kingdom of Absurdistan. There were N cities in the kingdom.

As it is often the case, some pairs of cities were connected by roads. The Great Vizier of Absurdistan was a terrible scrooge, hence the road network was a tree. (I.e., for any pair of cities there was exactly one way how to get from one to the other, while travelling by roads.)

The roads were made of concrete blocks and they all had a dull grey color.

One day, the Great Vizier came to the conclusion that travelling along dull grey roads makes people unhappy. As he does not want to risk a revolution, he decided to paint the roads using happy colors – the 7 colors of the rainbow.

Each day, he picked two cities s_{i} and t_{i}, and a color c_{i}. Painters with an ample supply of the color c_{i} were
sent to the city s_{i}, and then they travelled to t_{i}. On their way, whenever they encountered a road that did not
have the color c_{i}, they painted it to this color.

Problem specification

You are given the number of cities N, the description of the road network, and the sequence of Great Vizier’s orders.

For each order, compute the number of roads the painters had to repaint.

Input specification

The first line of the input file contains an integer T specifying the number of test cases. Each test case is preceded by a blank line.

Each test case starts with line containing a positive integer N (N ≤ 1000000). For convenience, the cities in Absurdistan are numbered 0 to N - 1.

N - 1 lines follow. Each of these lines contains two numbers a_{i} b_{i} (0 ≤ a_{i},b_{i} < N) – the endpoints of one
road.

The next line contains a single integer Q (Q ≤ 200000) specifying the number of orders.

Q lines follow, each describing one order. Each description consists of two integers s_{i} t_{i} (0 ≤ s_{i},t_{i} < N) and a
string c_{i} (c_{i} is one of red, orange, yellow, green, blue, indigo, and violet).

In the easy input, you may also assume that for each test case except for one we have NQ ≤ 10^{8}. In the
remaining test case the road network is a simple line.

Output specification

For each test case output seven lines. Each of these lines should contain a color name (in the order given above) and a number. The number shall be the total number of times some road was painted using the corresponding color.

You may output empty lines between the test cases. (The amount of whitespace in your output does not matter anyway; we do this for readability in the example below.)

Example

input
2
8 0 4 7 5 5 6 3 5 1 4 4 2 4 3 4 0 7 red 2 6 orange 4 3 green 1 7 green 12 0 1 1 2 2 3 2 4 2 5 0 6 6 7 7 8 7 9 7 10 11 6 3 3 8 blue 6 1 violet 5 11 blue |

output
red 4
orange 4 yellow 0 green 4 blue 0 indigo 0 violet 0 red 0 orange 0 yellow 0 green 0 blue 10 indigo 0 violet 2 We will explain the second test case in detail: When executing the query “3 8 blue”, we paint six roads blue: 3-2, 2-1, 1-0, 0-6, 6-7, and 7-8. When executing the query “6 1 violet”, we paint two roads violet: 6-0 and 0-1. (Both of these roads were previously blue.) Finally, when executing the query “5 11 blue”, we paint four roads blue: 5-2, 1-0, 0-6, and 6-11. Note that the road 2-1 was still blue, hence we did not paint it now. Thus we painted a road blue 6+4=10 times, and we painted a road violet 2 times. |