{"raw_statement":[{"iden":"problem statement","content":"You are given a sequence $A = (A_1, A_2, \\dots, A_N)$ of length $N$ consisting of $0$s and $1$s. Define a simple undirected graph $G = (V, E)$ with $\\frac{N (N - 1)}{2}$ vertices as follows:\n\n*   For every pair of integers $(i, j)$ satisfying $1 \\leq i < j \\leq N$, $(i, j) \\in V$. This vertex is called vertex $(i, j)$.\n*   For every triple of integers $(i, j, k)$ satisfying $1 \\leq i < j < k \\leq N$ and $A_i + A_j + A_k = 1$, there is an edge connecting vertex $(i, j)$ and vertex $(j, k)$.\n*   No other pairs of vertices have edges.\n\nDetermine the number of connected components in $G$.\nYou are given $T$ test cases. For each test case, compute the answer."},{"iden":"constraints","content":"*   All input values are integers.\n*   $1 \\leq T \\leq 10^5$\n*   $3 \\leq N \\leq 10^6$\n*   $A_i$ is $0$ or $1$ ($1 \\leq i \\leq N$)\n*   The total sum of $N$ over all test cases in a single input is at most $10^6$."},{"iden":"partial score","content":"$30$ points will be awarded for passing the test set satisfying the following constraints:\n\n*   $1 \\leq T \\leq 1000$\n*   $3 \\leq N \\leq 5000$\n*   The total sum of $N$ over all test cases in a single input is at most $5000$."},{"iden":"input","content":"The input is given in the following format:\n\n$T$\n$\\text{case}_1$\n$\\text{case}_2$\n$\\vdots$\n$\\text{case}_T$\n\nHere, $\\text{case}_i$ represents the $i$\\-th test case. Each test case is given in the following format:\n\n$N$\n$A_1$ $A_2$ $\\cdots$ $A_N$"},{"iden":"sample input 1","content":"4\n5\n1 0 0 1 0\n5\n1 1 1 1 1\n12\n0 0 1 1 1 0 0 0 1 0 1 0\n20\n0 0 1 0 0 1 1 1 0 0 1 0 0 1 1 1 1 0 1 1"},{"iden":"sample output 1","content":"4\n10\n13\n58\n\nFor the first test case, the connected components are as follows:\n\n*   $\\lbrace (1,2),(2,3),(2,4),(2,5),(3,4),(4,5) \\rbrace$\n*   $\\lbrace (1,3),(3,5) \\rbrace$\n*   $\\lbrace (1,4) \\rbrace$\n*   $\\lbrace (1,5) \\rbrace$\n\nFor the second test case, the graph has no edges, so the number of connected components is $10$."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}