{"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\"\u003eThere is a piece of paper in rectangular shape with sufficient length and width (lay flat on the table). Execute an operation instruction according to a string of length $n$ from left to right that only contains $4$ different characters of $L$,$R$,$U$,$D$.\u003cbr\u003e\u003cbr\u003e1. $L$ instruction means to fold it from left to right,\u003cbr\u003e\u003cbr\u003e2. $R$ instruction means to fold from right to left, \u003cbr\u003e\u003cbr\u003e3. $U$ instruction means to fold from top to bottom,\u003cbr\u003e\u003cbr\u003e4. $D$ instruction means to fold in half from bottom to top. \u003cbr\u003e\u003cbr\u003eNote that the operation is limited due to the limitation of the desktop. Namely, the fold operation is restricted. \u003cb\u003eFor example, if you fold the paper from left to right, you should let the left side overlap on the right side with no rotation.\u003c/b\u003e\u003cbr\u003e\u003cbr\u003eNow, cut a knife horizontally (completely cut) at the center of the visible part of the paper, and then cut vertically (completely cut).\u003cbr\u003e\u003cbr\u003eThe number of pieces of the whole paper split is $num(S)$.\u003cbr\u003e\u003cbr\u003e\u003cb\u003eSee the example and the picture for better understanding.\u003c/b\u003e\u003cbr\u003e\u003cbr\u003eNow given a nonnegative integer $n$, the string $S$ is generated from $4^n$ different possible outcomes in equal probability. Find the expected value of the number of pieces of the paper which is split, that is $E(num(S))$ mod $998244353$.\u003cbr\u003e\u003cbr\u003eIt can be shown that the answers can be represented by $\\frac{P}{Q}$, where $P$ and $Q$ are coprime integers, and print the value of $P \\times Q^{-1} \\ mod $ $\\space 998244353$.\u003cbr\u003e\u003ccenter\u003e\u003cimg style\u003d\"max-width:100%;\" src\u003d\"CDN_BASE_URL/f43dd687b477695ff799b3fce1e1225a?v\u003d1726186261\"\u003e\u003c/center\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line contains a single integer $ T $ ($1 \\le T \\le 10^5$), the number of testcases.\u003cbr\u003e\u003cbr\u003eEach of the next $ T $ lines contains a number $ n $ ( $0 \\le n \\le 10^{18} $ ).\u003cbr\u003e"}},{"title":"Output","value":{"format":"HTML","content":"For each testcase, print 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\u003e2\r\n0\r\n1\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e4\r\n6\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}