AT_arc233_c [ARC233C] Equal Degree Deletion

You are given a tree $ G $ with $ N $ vertices and $ N-1 $ edges. The vertices are numbered $ 1 $ to $ N $ , and the edges are numbered $ 1 $ to $ N-1 $ . Edge $ i $ connects vertices $ u_i $ and $ v_i $ . A tree $ H $ is called special if it is possible to delete all edges of $ H $ by performing the following operation zero or more times. - Choose an edge connecting two vertices whose current degrees are equal, and delete it. Find the number of special subtrees of $ G $ , modulo $ 998244353 $ . Solve $ T $ test cases for each input. What is a subtree? A subtree of a tree $ G $ is a connected subgraph of $ G $ .

The input is given from Standard Input in the following format: > $ T $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_T $ Each test case $ \mathrm{case}_t $ is given in the following format: > $ N $ $ u_1 $ $ v_1 $ $ u_2 $ $ v_2 $ $ \vdots $ $ u_{N-1} $ $ v_{N-1} $

Print $ T $ lines in total. The $ t $ -th line should contain the answer for the $ t $ -th test case.

### Sample Explanation 1 In the first test case, the $ 6 $ subtrees consisting of one vertex and the $ 5 $ subtrees consisting of two vertices and one edge are special. Also, the subtree of $ G $ consisting of vertices $ 1,3,4,6 $ and edges $ 1,3,5 $ is special, since the operation can be performed to delete edges $ 3,5,1 $ in this order. ### Constraints - $ 1 \leq T \leq 10^5 $ - $ 2 \leq N \leq 3 \times 10^5 $ - The sum of $ N $ over all test cases is at most $ 3 \times 10^5 $ . - $ 1 \leq u_i \lt v_i \leq N $ - The given graph $ G $ is a tree. - All input values are integers.