You are given a tree, i.e. a connected undirected graph with no cycles. For every two vertices x, y let d(x, y) denote the length (i.e. the number of edges) of the unique simple path between x and y. Count all the (unordered) triples {x, y, z} such that d(x, y) = d(y, z) = d(z, x) > 0.

Input

The first line contains the number of test cases z (1 ≤ z ≤ 20). The descriptions of the test cases follow.

The first line of every test case contains the number of vertices n (3 ≤ n ≤ 100 000). Each of the next n - 1 lines contains two integers a, b (1 ≤ a, b ≤ n), denoting that there is an edge between vertices a and b.

Output

For each test case output one integer: the number of triples in question.