Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

P132SUMC - SUM2 C - Mạng lưới giao thông

Tại đất nước Highland, có N thành phố được nối với nhau bởi N-1 con đường hai chiều. Chiều dài của mỗi con đường đúng bằng 1 km. Mạng lưới giao thông luôn đảm bảo rằng khi bạn xuất phát từ một thành phố, bạn có thể đi tới các thành phố bất kì khác.

Kinh tế năm qua phát triển rất nhiều, vì vậy nhà vua đã quyết định đầu tư thêm cho hệ thống giao thông của đất nước. Để giảm chi phí đi lại cho người dân cũng như hoạt động các hoạt động kinh tế, nhà vua quyết định mở thêm một tuyến đường giữa hai thành phố, sao cho độ ổn định của hệ thống giao thông là nhỏ nhất. Độ ổn định của hệ thống giao thông được tính bằng tất cả các tổng đường đi ngắn nhất giữa các cặp thành phố (có tất cả N*(N-1)/2 cặp thành phố).

Nhiệm vụ của các bạn là hãy giúp nhà vua tìm độ ổn định nhỏ nhất cho hệ thống giao thông của đất nước?

Input

Dòng đầu tiên là số lượng các bộ test T (T <= 20).

Với mỗi test, dòng thứ nhất chứa số nguyên N là số thành phố của đất nước (N <= 300).

N-1 dòng tiếp theo, mỗi dòng chứa hai số u, v biểu diễn con đường nối giữa thành phố u và v.

Output

Với mỗi test, hãy in ra độ ổn định nhỏ nhất của hệ thống giao thông.

Example

Input:

1
3
1 2
2 3 Output:
3

Giải thích: con đường mới nối thành phố 1 với thành phố 3.
Khi đó độ ổn định của hệ thống giao thông sẽ giảm từ 4 xuống còn 3.

Được gửi lên bởi:adm
Ngày:2013-07-19
Thời gian chạy:3s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.