CF2101A Mex in the Grid

You are given $ n^2 $ cards with values from $ 0 $ to $ n^2-1 $ . You are to arrange them in a $ n $ by $ n $ grid such that there is exactly one card in each cell. The MEX (minimum excluded value) of a subgrid $ ^{\text{∗}} $ is defined as the smallest non-negative integer that does not appear in the subgrid. Your task is to arrange the cards such that the sum of MEX values over all $ \left(\frac{n(n+1)}{2}\right)^2 $ subgrids is maximized. $ ^{\text{∗}} $ A subgrid of a $ n $ by $ n $ grid is specified by four numbers $ l_1, r_1, l_2, r_2 $ satisfying $ 1\le l_1\le r_1\le n $ and $ 1\le l_2\le r_2\le n $ . The element in the $ i $ -th row and the $ j $ -th column of the grid is part of the subgrid if and only if $ l_1\le i\le r_1 $ and $ l_2\le j\le r_2 $ .

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 100 $ ). The description of the test cases follows. The first line of each test case contains a single integer $ n $ ( $ 1\le n\le 500 $ ) — the side length of the grid. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 1000 $ .

For each test case, output $ n $ lines, each containing $ n $ integers representing the elements of the grid. If there are multiple answers, you can output any of them.

In the first test case, one valid arrangement is: 0123There are $ 9 $ subgrids in total, and the $ 4 $ of them with non-zero MEX are shown below: 0 values: $ [0] $ — MEX: $ 1 $ 01 values: $ [0, 1] $ — MEX: $ 2 $ 02 values: $ [0, 2] $ — MEX: $ 1 $ 0123 values: $ [0, 1, 2, 3] $ — MEX: $ 4 $ The sum of MEX over all subgrids would be $ 1+2+1+4 = 8 $ . It can be proven that no other arrangements have a larger sum of MEX values.