Hackerland is a big country with n cities and some roads. The cities are numbered from 1 to n. The city numbered 1 is the capital city. The people of Hackerland are very smart. They figured out that they need to build only n-1 roads to make travelling between each pair of cities possible. They built the roads in such a way that there exists a unique way to reach a city from each other city.
The roads have the following properties:
- Each road connects two cities, x and y. Keep in mind that out of x and y, one will be closer to the capital city than the other.
- Each road is a one-way road. Meaning that travelling is possible only from one of the two cities to the other and not in both directions.
- The direction of each road changes after one day. On day 1, all roads allow traffic to go away from the capital city. Then on day 2, all roads allow traffic to go towards the capital city. On day 3, again away from the capital city, and so on.
Given a source and destination city, your job is to find the number of days required to complete the journey. Assume that travelling on one road requires a whole day.
Input:
The first line of input contains t, the number of test cases.
The first line of each test case contains n, the number of cities. n-1 lines follow. Each line has two integers x and y, signifying that city x and city y are connected by a road. The next line contain q, the number of queries. Each of the next q lines contains two integers, a and b.
Output:
For each query output a single integer denoting the number of days required to travel from city a to city b. (a!=b)
Constraints:
1<=t<=5
2<=n<= 10000
1<=q<=100000
WARNING : Large input data. Be careful with certain languages.
C++ users: Use scanf instead of cin