{"raw_statement":[{"iden":"problem statement","content":"You are given an $N\\times N$ matrix $A = (A_{i,j})$ ($1\\le i,j\\le N$) whose entries are $0$ or $1$.\nFind, modulo $998244353$, the number of trees $G$ on $N$ vertices numbered $1$ to $N$ that satisfy the following condition.\n\n*   $A_{i,j}=1$ if and only if at least one of the following holds:\n    *   When $G$ is rooted at vertex $1$, Vertex $j$ is an ancestor of vertex $i$. That is, vertex $j$ lies on the unique path in $G$ between vertices $1$ and $i$.\n    *   When $G$ is rooted at vertex $1$, Vertex $i$ is an ancestor of vertex $j$. That is, vertex $i$ lies on the unique path in $G$ between vertices $1$ and $j$.\n\nHere, the endpoints of a path are considered to be on that path. Note that $G$ being a tree guarantees uniqueness of the path between any two vertices.\nThere are $T$ test cases; solve each one."},{"iden":"constraints","content":"*   $1\\leq T\\leq 10^5$\n*   $2\\leq N\\leq 400$\n*   $A_{i,j}\\in \\lbrace 0,1\\rbrace$ $(1\\leq i,j\\leq N)$\n*   $A_{i,i}=1$ $(1\\leq i\\leq N)$\n*   $A_{i,j}=A_{j,i}$ $(1\\leq i,j\\leq N)$\n*   The sum of $N^2$ over all test cases is at most $400^2$."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$T$\n$\\text{case}_1$\n$\\vdots$\n$\\text{case}_T$\n\nEach case is given in the following format:\n\n$N$\n$A_{1,1}$ $\\cdots$ $A_{1,N}$\n$\\vdots$\n$A_{N,1}$ $\\cdots$ $A_{N,N}$"},{"iden":"sample input 1","content":"5\n3\n1 1 1\n1 1 0\n1 0 1\n3\n1 1 1\n1 1 1\n1 1 1\n3\n1 0 0\n0 1 0\n0 0 1\n3\n1 0 1\n0 1 1\n1 1 1\n7\n1 1 1 1 1 1 1\n1 1 0 1 0 1 1\n1 0 1 1 1 1 0\n1 1 1 1 1 1 1\n1 0 1 1 1 1 0\n1 1 1 1 1 1 1\n1 1 0 1 0 1 1"},{"iden":"sample output 1","content":"1\n2\n0\n0\n8\n\nIn the first test case, the following one tree $G$ satisfies the condition: ![image](https://img.atcoder.jp/arc197/047f79d01c371fe5f47850c631892671.png)\nIn the second test case, the following two trees $G$ satisfy the condition: ![image](https://img.atcoder.jp/arc197/ff998867883faff858791a57f8497f6d.png)"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}