SP1465 CHRIS - On the Way to Find Chris

Do you know the famous game THE KING OF FIGHTERS? If the answer is yes, I'm sure you know THE THREE BLACK GROUP: Chris, Shermie and Yashiro. Today Chris is invited to one of his friends' home to play THE KING OF FIGHTERS.Blue Mary is now at Chris' home, she knows where Shermie's and Yashiro's home is, but she doesn't know where Chris actually is.So she decides that: - If Yashiro's home is nearer than Shermie's, she will go to Yashiro's home first, if she doesn't find Chris, she will then go to Shermie's, and vice versa. - The map of the city is strange. Each of the houses is assigned to a unique number in the range\[1,n\], where n is the number of houses. Between some pairs of houses there are some roads. There exists one and only one path from any house to any other house. She will go along the only path between the two houses.

The number of test cases T is given in the very first line.T blocks follow. For each test case, the first line contains 2 space-separated integers N(3

For each test case you should output a single line, which contains a single integer - the maximum time measured in minutes.