给定一棵树，即一个无环连通无向图。对于任意两个顶点 $x, y$，令 $d(x, y)$ 表示 $x$ 和 $y$ 之间唯一简单路径的长度（即边的数量）。请统计所有满足 $d(x, y) = d(y, z) = d(z, x) > 0$ 的（无序）三元组 $\{x, y, z\}$ 的数量。
输入格式
输入的第一行包含测试用例的数量 $z$ ($1 \le z \le 20$)。接下来是各测试用例的描述。
每个测试用例的第一行包含顶点数 $n$ ($3 \le n \le 100\,000$)。接下来的 $n - 1$ 行，每行包含两个整数 $a, b$ ($1 \le a, b \le n$)，表示顶点 $a$ 和 $b$ 之间有一条边。
输出格式
对于每个测试用例，输出一个整数：满足条件的三元组数量。
样例
输入 1
2 4 1 2 1 3 1 4 8 1 2 1 3 1 4 2 5 2 6 3 7 4 8
输出 1
1 4