拉网线

Time Limit: 4000MS

Memory Limit: 655350KB

Description

小明要给一个乡村的所有居民铺设网络,这个乡村总共有N户居民,为了节约网线,老板要求小明所使用的网线总长度最短,并且所有人都可以上网。

当然,这个要求对于小明来说毫无压力,正当小明准备工作的时候,老板又来了,他告诉小明,这些居民中有两家A,B非常不和睦,所以千万不要在A,B之间拉网线,而应该通过第三方C供网。遗憾的是老板不知道哪两家人不和睦。老板希望小明拿出一个万全的方案,无论哪两户人家不合都能很快的知道网线总长度。

Input

第一行 T,表明case数。(T<=30)

第二行 N.表示居民数(3<= N <= 3000)。

接下来N-1行,第一行有一个整数,第二行有两个整数,依次类推,第N-1行有N-1个整数,其中每一行的第一个数表示到居民0的距离,其他依次类推。例如,样例中的第二行 第一个数表示居民2到居民0的距离,第二个数表示居民2到居民1的 距离。

接下来一个整数Q(Q<= 100000)

接下来Q行,每行输入两个整数0<=A,B<N。(A != B)表示A,B之间不和睦。

Output

Q次查询的平均网线长度(保留四位有效数字)。

Sample Input

1
3
7
10 5
3
2 1
2 0
1 0

Sample Output

14.6667

Hint

None

Source

陈龙

提交代码