There are n cities in the Rainbow Island, connected by n−1 bidirectional roads.
Lizishu is fond of travel. In the ith of each m years, she would go for travel from city xi with ki Yuan and she would cost 1 Yuan leaving a city to an adjacent one. For seeing more scenery, she wants to go to as many different cities as possible.
Now you are given the map of the Rainbow Island and you should tell Lizishu the maximum number of different cities (including xi) she can reach every year.
Note that every time she can only go to an adjacent city and cost 1 Yuan.
输入描述:
The first line contains an integer number T, the number of test cases.
For each test case :
The first line contains an integer n(1 ≤ n ≤ 105), the number of vertices.
The following n−1 lines, each contains two integers u,v(1 ≤ u,v ≤ n), which means there is an edge between u and v.
It is guaranteed that the graph is connected.
The next line contains an integer m(1 ≤ m ≤ 106), the number of years.
The following m lines, the ith line contains two integers xi(1 ≤ xi≤ n),ki(1 ≤ ki≤ 106), the index of the city she starts travel and the money she carries in the ith year.
输出描述:
For each year print the answer.
示例1
输入
复制
1
6
1 2
1 3
2 4
2 5
3 6
2
2 2
2 4