You are given a tree with $$$n$$$ vertices, where each vertex can be colored red, blue, or white. The coolness of a coloring is defined as the maximum distance$$$^{\text{∗}}$$$ between a red and a blue vertex.

Formally, if we denote the color of the $$$i$$$-th vertex as $$$c_i$$$, the coolness of a coloring is $$$\max d(u, v)$$$ over all pairs of vertices $$$1\le u, v\le n$$$ where $$$c_u$$$ is red and $$$c_v$$$ is blue. If there are no red or no blue vertices, the coolness is zero.

Your task is to calculate the sum of coolness over all $$$3^n$$$ possible colorings of the tree, modulo $$$998\,244\,353$$$.

$$$^{\text{∗}}$$$The distance between two vertices $$$a$$$ and $$$b$$$ in a tree is equal to the number of edges on the unique simple path between vertex $$$a$$$ and vertex $$$b$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 50$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$2\le n\le 3000$$$) — the number of vertices in the tree.

Each of the next $$$n - 1$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1\le u, v\le n$$$) — the endpoints of the edges of the tree.

It is guaranteed that the given edges form a tree.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$3000$$$.

Output

For each test case, output the sum of coolness over all $$$3^n$$$ possible colorings of the tree, modulo $$$998\,244\,353$$$.

Note

In the first test case, there are $$$12$$$ colorings that have at least one blue and one red node. The following pictures show their coloring and their coolness:

$\text{[math]}$ All these colorings have coolness $$$2$$$ $\text{[math]}$ All these colorings have coolness $$$1$$$

Therefore, the sum of coolness over all possible colorings is $$$6\cdot 2 + 6\cdot 1 = 18$$$.

In the second test case, the following are some examples of colorings with a coolness of $$$3$$$:

$\text{[math]}$

Shoo Shatters the Sunshine

Examples