{"raw_statement":[{"iden":"problem statement","content":"For a sequence $X=(X_1,X_2\\ldots,X_N)$ of length $N$ consisting of positive integers, we define $f(X)$ as follows:\n\n*   A tree with $N$ vertices is said to be good if and only if the degree of the $i$\\-th $(1 \\leq i \\leq N)$ vertex is $X_i$. If a good tree exists, $f(X)$ is the maximum diameter of a good tree; if it doesn't, $f(X)=0$.\n\nHere, the distance between two vertices is the minimum number of edges that must be traversed to travel from one vertex to the other, and the diameter of a tree is the maximum distance between two vertices.\nFind the sum, modulo $998244353$, of $f(X)$ over all possible sequences $X$ of length $N$ consisting of positive integers. We can prove that the sum of $f(X)$ is a finite value.\nGiven $T$ test cases, find the answer for each of them."},{"iden":"constraints","content":"*   $1\\leq T \\leq 2\\times 10^5$\n*   $2 \\leq N \\leq 10^6$\n*   All values in the input are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format, where $\\mathrm{test}_i$ denotes the $i$\\-th test case:\n\n$T$\n$\\mathrm{test}_1$\n$\\mathrm{test}_2$\n$\\vdots$\n$\\mathrm{test}_T$\n\nEach test case is given in the following format:\n\n$N$"},{"iden":"sample input 1","content":"10\n2\n3\n5\n8\n13\n21\n34\n55\n89\n144"},{"iden":"sample output 1","content":"1\n6\n110\n8052\n9758476\n421903645\n377386885\n881422708\n120024839\n351256142\n\nIf $N=3$,\nfor example,\n\n*   when $X=(1,1,1)$, there is no tree with three vertices whose degrees are $1,1$, and $1$, so $f(X)=0$.\n*   When $X=(2,1,1)$, the only possible tree is illustrated below. The diameter of this tree is $2$, so $f(X)=2$.\n\n  \n![image](https://img.atcoder.jp/abc290/7b4cd8233d2ee3eb307023bebaebd906.jpg)  \n  \n\nFor $X=(2,1,1),(1,2,1),(1,1,2)$, we have $f(X)=2$; for other $X$, we have $f(X)=0$. Thus, the answer is $6$."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}