A coal mine can be viewed as an undirected graph consisting of mining points connected by tunnels. For safety reasons, it is hoped that in the event of an accident at the site, all workers at the mining points will have a path to escape to a rescue exit. Therefore, the mine owner decides to set up rescue exits at certain mining points such that even if any one mining point collapses, workers at all other mining points will still have a path to a rescue exit.

Please write a program to calculate the minimum number of rescue exits required, as well as the total number of different ways to set up this minimum number of rescue exits.

Input

The input contains several test cases. The first line of each test case is a positive integer $N$ ($N \le 500$), representing the number of tunnels in the mine. The following $N$ lines each contain two space-separated integers $S$ and $T$, representing that mining point $S$ and mining point $T$ are directly connected by a tunnel. The input is terminated by $0$.

Output

The output file should contain as many lines as there are test cases in the input file. Each line corresponds to the result of one test case. Each line starts with Case i: (note the capitalization, there is a space between Case and i, no space between i and :, and a space after :), followed by two space-separated positive integers. The first integer represents the minimum number of rescue exits required for the $i$-th test case, and the second integer represents the total number of different ways to set up this minimum number of rescue exits. The input data guarantees that the answer is less than $2^{64}$. Please refer to the sample input and output for the format.

Examples

Input 1

9
1 3
4 1
3 5
1 2
2 6
1 5
6 3
1 6
3 2
6
1 2
1 3
2 4
2 5
3 6
3 7
0

Output 1

Case 1: 2 4
Case 2: 4 1

Note

For Case 1, the four sets of solutions are $(2,4), (3,4), (4,5), (4,6)$. For Case 2, the one set of solutions is $(4,5,6,7)$.