Endless Pallet

There is a tree formed by N nodes. Initially, all the nodes are in white color. If there is at least one white node on the tree, Ash will randomly choose a path on the tree and dye all the nodes in the path black. Otherwise, Ash will stop dyeing and go home.

Given the tree, can you calculate the expected number of the paths Ash choose?

There are paths in total, that is, path from u to v and path from v to u are the same. It is okay to choose a path with no white node, but Ash will stop dyeing immediately when there are no white nodes on the tree.

输入描述:

The input starts with one line containing exactly one integer T, which is the number of test cases.

Each test case starts with one line containing exactly one integer N, indicating the size of the tree.

Then followed by N lines, each consists of 2 numbers ui, vi, indicating the i-th edge of the tree is between ui and vi.
- 1 ≤ T ≤ 15.
- 1 ≤ N ≤ 50.
- 1 ≤ ui, vi ≤ n.

输出描述:

For each test case, output one line containing "Case #x: y", where x is the test case number (starting from 1) and y is the expected number of the paths Ash choose.

In order to avoid floating point arithmetic, you are supposed to output y modulo 998244353, that means if the answer is equal to , you should output .

3
1
2
1 2
3
2 3
1 3

Case #1: 1
Case #2: 2
Case #3: 698771050