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). 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). For each test case, output the sum of coolness over all (3^n) possible colorings of the tree, modulo (998\,244\,353). 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: 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):