Interesting Triplets (Easy)

Niko just learned about tree. Not those give us oxygen but tree from graph theory. After a while, he figured out that if he takes three distinct nodes A, B, C from a tree, sometimes it may occur that sum of the shortest distance from A to B and from B to C is equal to the shortest distance from A to C. This breathtaking discovery excites Niko a lot. He named such triplet as an interesting triplet. Out of curiosity, Niko tried to count down the number of such interesting triplets in a given tree. But alas, he is a newbie in graph theory and messed around the calculation. Niko heard that you are one of the best programmers from NSU and you are going to participate in “Intra NSU Programming Contest 2018”. So he came to you and ask for your help. Help Niko to solve his problem.

Input

Input starts with an integer T (≤ 100), denoting the number of test cases.

Each case starts with a integers n (1 ≤ n ≤ 20) donating the number of nodes. The next n-1 lines contain two integers u, v (1 ≤ u, v <= n, u ≠ v) indicating that there is an edge between u and v. There’ll be exactly one path between any pair of nodes u and v.

Note: This is the easier version of the problem. The harder version is exactly the same problem except the constraints are different.

Output

For each case, print a line containing the case number and the number of interesting triplets.

Sample

Input	Output
2 3 1 2 2 3 2 1 2	Case 1: 2 Case 2: 0

For case 1, interesting triplets are (1,2,3) and (3,2,1)

For case 2, there is no interesting triplet.