**Please Note: This is not an on-going Challenge question**

**Question :**

There are N cities in the Byteland which are connected by N-1 bidirectional roads. Given two cities of the Byteland u and v. Now, you have to find the tow cities x and y of the Byteland such that the path between these tow cities overlaps the path between the given cities u and v completely and the gcd(x,y) is maximum possible.

**Note:** It is guaranteed that the graph is connected.

**Input Format**

The first line of the input contains an integer T, the total number of test cases.

Then T test cases follow, the first line of each test case contains an integer N, the total number of cities in the Byteland.

Then N-1 lines follow, the first line of each test case contains two separated integers a and b representing that there is a bidirectional road between the city a and b.

The next line contains two space-separated integers u and v.

**Output Format**

In the single line of the output print an integer representing the maximum possible gcd of the cities x and y.

**Constraints**

1 \leq T \leq 10

1 \leq N \leq 5 \times 10^{5}

1 \leq a,b,u,v \leq N

**Sample Input**

$2 \

6 \

1 , , , , 2 \

1 , , , , 3 \

2 , , , , 4 \

2 , , , , 5 \

2 , , , , 6 \

1 , , , , 3 \

10 \

1 , , , , 4 \

1 , , , , 5 \

1 , , , , 2 \

4 , , , , 3 \

4 , , , , 6 \

5 , , , , 7 \

2 , , , , 10 \

2 , , , , 9 \

2 , , , , 8 \

4 , , , , 2 \$

**Sample Output**

3 \\ 4

**Explaination :**

Sample test case 2:

The path from u to v is 4 \rightarrow 1 \rightarrow 2

Now, some of the paths which are completely overlaps the path from u to v are:

4 \rightarrow 1 \rightarrow 2 \rightarrow 10 \\ 3 \rightarrow 4 \rightarrow 1 \rightarrow 2 \rightarrow 9 \\ 4 \rightarrow 1 \rightarrow 2 \rightarrow 8

and so on…

Note that, selecting the path from 4 to 8 completely overlaps the path u and v, and also the gcd(4,8) = 4 which is the maximum possible.

**Time Limit:** 3.0 sec(s) for each input file

I have thought of finding all paths between every two pair of vertices and store them. Then find whether u and v is contained in them. For all paths which satisfies the previous conditions, I will find gcd of the end points of the path. But this seems too complex. I guess it could be solved in other simple way. But I couldn’t think of any other way. Can anyone suggest what to do. I could post my code link if it is needed. Thanks.