{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003eCuber QQ knows about DFS on an undirected tree, he\u0027s sure that you are familiar with it too. In case you are not, Cuber QQ is delighted to share with you a snippet of pseudo code:\u003cbr\u003e\u003cbr\u003e\u003cpre\u003e\u003cbr\u003efunction dfs(int cur, int parent):\u003cbr\u003e print(`(`)\u003cbr\u003e for all nxt that cur is adjacent to:\u003cbr\u003e dfs(nxt, cur)\u003cbr\u003e print(`)`)\u003cbr\u003e\u003c/pre\u003e\u003cbr\u003e\u003cbr\u003eYou might notice that Cuber QQ print a \"(\" when entering a node, and a \")\" when leaving a node. So when he finishes this DFS, in his console, he will see a bracket sequence of length $2n$, where $n$ is the number of vertices in the tree.\u003cbr\u003e\u003cbr\u003eObviously, if the tree is undirected and the nodes are unlabelled (meaning that all the nodes are treated equally), you can get a lot of different bracket sequences when you do the DFS. There are two reasons accounting for this. Firstly, when you are at cur, you can follow any permutation of the nodes that cur is adjacent to when you visit nxt. Secondly, the entrance to the tree, that is the root, is undeterministic when you start your DFS.\u003cbr\u003e\u003cbr\u003eSo Cuber QQ couldn\u0027t help wondering how many distinct bracket sequences he can get possibly. As the answer can be very large, output it modulo $998~244~353$.\u003cbr\u003e\u003cbr\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line of the input consists of one integer $t$ ($1 \\le t \\le 10^5$), which is the number of the test cases.\u003cbr\u003e\u003cbr\u003eFor each test case, the tree is given in a standard format, which you might be very familiar with: first line $n$ ($1 \\le n \\le 10^5$), the size of tree; then $n-1$ lines, each consisting of two space-separated integers $u$, $v$ ($1 \\le u, v \\le n$, $u \\ne v$), denoting an edge.\u003cbr\u003e\u003cbr\u003eThe sum of $n$ from all test cases does not exceed $3.2 \\times 10^6$."}},{"title":"Output","value":{"format":"HTML","content":"For each test case, output the answer in one line."}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\r\n4\r\n1 3\r\n2 3\r\n4 3\r\n5\r\n1 2\r\n2 3\r\n3 4\r\n4 5\r\n5\r\n1 2\r\n2 3\r\n3 4\r\n3 5\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\r\n4\r\n8\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}