{"raw_statement":[{"iden":"statement","content":"You are given a grid consisting of n rows each of which is dived into n columns. The rows are numbered from 1 to n from top to bottom, and the columns are numbered from 1 to n from left to right. Each cell is identified by a pair (x, y), which means that the cell is located in the row x and column y. All cells in the grid contain positive integers.\n\nYour task is to choose a subset of the grid's cells, such that their summation is as maximal as possible, and there are no two adjacent cells in that subset. Two cells are considered adjacent if they are horizontal, vertical, or diagonal neighbors.\n\nThe first line contains an integer T (1 ≤ T ≤ 100), in which T is the number of test cases.\n\nThe first line contains an integer n (1 ≤ n ≤ 16), in which n is the number of rows and columns in the grid. \n\nThen n lines follow, each line contains n integers, giving the grid. All values in the grid are between 1 and 1000 (inclusive).\n\nFor each test case, print a single line containing the maximum sum of a subset of the grid's cells. The chosen subset must not contain any adjacent cells. \n\n"},{"iden":"input","content":"The first line contains an integer T (1 ≤ T ≤ 100), in which T is the number of test cases.The first line contains an integer n (1 ≤ n ≤ 16), in which n is the number of rows and columns in the grid. Then n lines follow, each line contains n integers, giving the grid. All values in the grid are between 1 and 1000 (inclusive)."},{"iden":"output","content":"For each test case, print a single line containing the maximum sum of a subset of the grid's cells. The chosen subset must not contain any adjacent cells. "}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ a, b, c, h \\in \\mathbb{Z}_{\\geq 0} $ be the damage values of Alpha, Beta, Charlie variations and Lavos’s health, respectively.  \nLet $ p \\in \\{R, N, E\\}^* $ be Lavos’s attack pattern of length $ m = |p| $.  \nLet $ t \\in \\{A, B, C\\}^* $ be the Omnislash sequence of length $ n = |t| $, with $ n \\leq m $.  \n\nDefine a mapping $ \\sigma: \\{R, N, E\\} \\to \\{a, b, c\\} $:  \n- $ \\sigma(R) = a $,  \n- $ \\sigma(N) = b $,  \n- $ \\sigma(E) = c $.  \n\nDefine a mapping $ \\tau: \\{A, B, C\\} \\to \\{a, b, c\\} $:  \n- $ \\tau(A) = a $,  \n- $ \\tau(B) = b $,  \n- $ \\tau(C) = c $.  \n\n**Constraints**  \n1. $ 0 \\leq a, b, c \\leq 10^9 $  \n2. $ 1 \\leq h \\leq 10^9 $  \n3. $ 1 \\leq |p| \\leq 2 \\times 10^5 $  \n4. $ 1 \\leq |t| \\leq |p| $  \n\n**Objective**  \nLet $ k \\in \\{0, 1, \\dots, m - 1\\} $ be the initial offset of Lavos’s pattern, chosen uniformly at random.  \nFor each $ k $, define the total damage dealt during Omnislash as:  \n$$\nD_k = \\sum_{i=0}^{n-1} \\tau(t[i]) \\cdot \\mathbf{1}_{\\tau(t[i]) = \\sigma(p[(k+i) \\bmod m])}\n$$  \nLavos is defeated if $ D_k \\geq h $.  \n\nCompute the probability:  \n$$\n\\mathbb{P} = \\frac{1}{m} \\cdot \\left| \\left\\{ k \\in \\{0, \\dots, m-1\\} \\mid D_k \\geq h \\right\\} \\right|\n$$  \nOutput $ \\frac{p}{q} $ as an irreducible fraction.","simple_statement":"You are fighting Lavos, a boss with a repeating attack pattern. You must use a fixed attack sequence (Omnislash) as soon as Lavos starts. Each attack in Lavos’s pattern matches one of your attacks, dealing fixed damage. You win if total damage ≥ Lavos’s HP. Lavos starts at a random position in its pattern. Find the probability you win, as a reduced fraction.","has_page_source":false}