{"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\"\u003eNamesolo has fallen in love with the game \u003ci\u003eStick Fight\u003c/i\u003e. But when he is playing the game, he wonders how to find out the number of stickmen in the game.\u003cbr\u003e\u003cbr\u003e\u003ccenter\u003e\u003cimg style\u003d\"max-width:100%;\" src\u003d\"CDN_BASE_URL/3d761957a78ecba1f7055ec5cf590c77?v\u003d1713707340\"\u003e\u003c/center\u003e \u003cbr\u003e\u003cbr\u003eIn this question, we define the stick man as shown in the picture above. It has a chain of length $1$ as the head, two chains of length $2$ as the arms, a chain of length $1$ as the body, and two chains of length $1$ as the legs. For example, the red part in this picture can be viewed as a stick man, with chain $(2,3)$ to be the head, chains $(3,4,6)$ and $(3,9,10)$ to be the arms, chain $(3,5)$ to be the body, and chains $(5,7)$ and $(5,8)$ to be the legs.\u003cbr\u003e\u003cbr\u003eThe game can be viewed as a tree, and Namesolo wants to know how many stickmen are there. Please note that two stickmen are different when there is at least one different edge between the two edge sets that make up the two stickmen.\u003cbr\u003e\u003cbr\u003eBecause the answer may be too large, Namesolo wants to know the answer modulo $998244353$.\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line of input contains one integer $T\\ (1\\le T\\le 15)$, indicating the number of test cases.\u003cbr\u003e\u003cbr\u003eFor each test case, the first line contains an integer $n$ ($1\\le n \\le 5\\times 10^5$), indicating the number of vertices in the tree. Each of the following $n-1$ lines contains two integers $a,b$ ($1 \\le a,b \\le n$), indicating that there is an edge connecting $a$ and $b$ in the tree.\u003cbr\u003e\u003cbr\u003eIt is guaranteed that the sum of $n$ over all cases won\u0027t exceed $3 \\times 10^6$."}},{"title":"Output","value":{"format":"HTML","content":"For each test case, output an integer representing the answer modulo $998244353$."}},{"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\u003e1\r\n9\r\n1 2\r\n2 3\r\n3 4\r\n2 5\r\n5 6\r\n2 7\r\n7 8\r\n7 9\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}