ami có một cái cây \(N\) đỉnh, gốc là 1. Các bạn cần tính các thông số sau:

1) \(\sum w[i] \cdot i\) với \(w[x]\) là số nút con trong cây con có gốc là \(x\)

2) \(\sum (h[i]+1) \cdot i\) với \(h[x]\) là \(\max(f[x][v])\) với \(v\) là một cháu của \(x\).

3) \(\sum f[u][v]\) với mọi \(u \geq v\).

\(f[u][v]\) là độ dài đường đi từ \(u\) đến \(v\). Độ dài đường đi giữa 2 nút \(u\) và \(v\) được tính bằng số cạnh trên đường đi ngắn nhất từ \(u\) đến \(v\).

Input

• Dòng đầu tiên chứa \(t\) là số câu hỏi.
• Mỗi câu hỏi có dạng sau:
  • Dòng đầu tiên chứa 1 số nguyên \(N\) là số đỉnh của cây.
  • \(N-1\) dòng tiếp theo, mỗi dòng chứa 2 số nguyên dương \(u\) và \(v\) biểu thị một cạnh nối.

Output

• 3 số nguyên \(a\), \(b\), \(c\) với \(a\) là thông số 1), \(b\) là thông số 2), \(c\) là thông số 3).

Example

1
3
1 2
2 3

10 10 4

Giới hạn

• \(\sum N \leq 2 \cdot 10^6\)
• \(1 \leq u, v \leq N\)
• \(1 \leq N \leq 2 \cdot 10^5\)