Cho đồ thị cây có trọng số gồm ~N~ đỉnh, các đỉnh được đánh số từ ~1 \rightarrow N~. Gốc của cây là đỉnh ~1~. Cha của đỉnh ~u~ là ~1~ đỉnh có số hiệu nhỏ hơn ~u~. Mỗi đỉnh có một nhãn là ~1~ số thực ~A[i]~. Trong đó nhãn của đỉnh ~1~ bằng ~1~ và nhãn của đỉnh lá bằng ~0~. Biết rằng ~A[v] \leq A[u]~ nếu ~v~ là con của ~u~.

Giá trị của ~1~ cây là Tổng ~((A[u] - A[v]) \times~ trọng số cạnh ~(u, v)~, với ~u~ là cha của ~v)~

Bây giờ người ta cho biết các cạnh của đồ thị và trọng số của các cạnh này nhưng không cho biết các ~A[i]~. Hãy tính xem giá trị của cây thấp nhất là bao nhiêu.

Input

Dòng ~1~ là số nguyên ~T~ là số bộ test. ~(1 \leq T \leq 50)~. ~T~ nhóm dòng tiếp theo mô tả từng bộ test. Mỗi bộ test sẽ có cấu trúc như sau:

Dòng ~1~: số nguyên dương ~N~ ~(1 \leq N \leq 1000)~.

Từ dòng ~2 \rightarrow~ dòng ~N~: dòng thứ ~i~ gồm ~2~ số nguyên dương ~u~ và ~c~ ~(1 \leq u < i~, ~0 \leq c \leq 1000)~ cho biết cha của nút ~i~ là nút ~u~ và cạnh nối ~(u~, ~i)~ có trọng số là ~c~.

Output

Với mỗi test ghi ra giá trị thấp nhất có thể đạt được của cây trên ~1~ dòng với độ chính xác là ~2~ chữ số sau dấu chấm.

Sample Input

1
4
1 1
1 2
2 1

Sample Output

3.00