William was still annoyed with Yuhao since he told William about prime numbers, after knowing that prime numbers do not have any divisors except 1 and itself. William only likes non-prime numbers. To give their friendship another chance, Yuhao decided to give William a problem:

Given a tree with $N$ nodes, find the size of the largest subtree which does not contain any prime number. The nodes are numbered from $0$ to $N-1$, where $0$ is the root. The value of a node is defined as the sum of the node-numbers on all of its neighbours. A subtree is said to contain a number if this number is the value of a node in the subtree.

Input

The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.

The first line of each test case contains a single integer, $N$.

Each of the next $N-1$ lines contains two space-separated integers $x$ and $y$ denoting that $x$ and $y$ have an edge in the tree.

Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is "BAD TREE!" (without quotes) if there is no subtree that does not contain any prime number. Otherwise, it is the integer denoting the answer to the problem.

Constraints

The trees are generated at random.

$1\le T \le10^5$

$1\le N \le10^{5}$

Sum over all test cases does not exceed $5 \cdot 10^6$.

Problem Author: Ankit Kumar Singh