Coprime Grid

In this solution, rows and columns are indexed from $0$. Thus the row index is one of $0,1,2,3,4$, and the column index is one of $0,1,\cdots,2N-1$.

First, use the sieve of Eratosthenes to compute all primes up to $2\max N_i$. For each $N$, choose two primes $p,q$ such that $2N=p+q$, with . In the implementation, it is enough to check primes close to first. Under the constraints of this problem, such a pair exists for every required .

The main idea is to split the grid into a left block of width $p$ and a right block of width $q$. We first describe the general case, where $p<q$ and $p\notin\{3,5,7\}$. Initially define

$$A_{r,c}= \begin{cases} 1+c+rp & (0\leq c<p),\\ 6p-c+(5-r)q & (p\leq c<p+q). \end{cases}$$

The left block uses exactly the numbers $1,2,\cdots,5p$, and the right block uses exactly the numbers $5p+1,5p+2,\cdots,5p+5q$. Hence the whole grid is a permutation of .

Inside the left block, horizontally adjacent numbers differ by $1$, so all horizontal pairs are coprime. Vertically adjacent numbers differ by exactly $p$. Therefore, if a vertical pair in the left block is not coprime, both numbers must be multiples of $p$. This happens only in the last column $c=p-1$, where the column is

$$p,\ 2p,\ 3p,\ 4p,\ 5p.$$

The right block is analogous. Horizontally adjacent numbers differ by $1$, so all horizontal pairs are coprime. Vertically adjacent numbers differ by exactly $q$, so the only dangerous column is the column containing multiples of $q$.

We now fix these two columns.

First, fix the column of multiples of $p$ in the left block. Originally, $A_{0,1}=2$, $A_{0,3}=4$, , and . Replace these values as follows:

$$A_{0,1}=2p,\quad A_{0,3}=4p,\quad A_{1,p-1}=2,\quad A_{3,p-1}=4.$$

Then the last column of the left block becomes

$$p,\ 2,\ 3p,\ 4,\ 5p.$$

The adjacent pairs in this column are $(p,2)$, $(2,3p)$, $(3p,4)$, and $(4,5p)$, and all of them are coprime because is an odd prime.

We also need to check the other edges affected by this replacement. The value $2p$ is placed between $1$ and $3$, and the value below it is $p+2$. Since $p\notin\{2,3\}$, all these pairs are coprime. Similarly, is placed between and , and the value below it is ; since , no bad pair is created. The values and placed in the last column are also adjacent only to odd numbers or to numbers not divisible by the relevant small factors, so they create no bad pair.

Next, find the column of multiples of $q$ in the right block. Let

$$k=\left\lfloor\frac{5p}{q}\right\rfloor$$

and

$$l=6p-kq.$$

Then the multiples of $q$ are gathered in column $l$. More precisely, column $l$ contains

$$(k+5)q,\ (k+4)q,\ (k+3)q,\ (k+2)q,\ (k+1)q$$

from top to bottom.

If $k$ is even, apply the following replacements:

$$A_{0,k}=(k+1)q,\quad A_{0,k+2}=(k+3)q,\quad A_{0,k+4}=(k+5)q,$$ $$A_{0,l}=k+5,\quad A_{2,l}=k+3,\quad A_{4,l}=k+1.$$

In other words, we swap the odd-indexed multiples of $q$ with small numbers in the first row. Column $l$ then becomes

$$k+5,\ (k+4)q,\ k+3,\ (k+2)q,\ k+1.$$

Small numbers and multiples of $q$ now alternate. Each small number is coprime to the neighboring coefficient and is smaller than $q$, so all vertical pairs in this column are coprime.

If $k$ is odd, apply the following replacements instead:

$$A_{0,k+1}=(k+2)q,\quad A_{0,k+3}=(k+4)q,$$ $$A_{1,l}=k+4,\quad A_{3,l}=k+2.$$

Then column $l$ becomes

$$(k+5)q,\ k+4,\ (k+3)q,\ k+2,\ (k+1)q.$$

Again, small numbers and multiples of $q$ alternate, so all vertical pairs in this column are coprime.

The moved multiples of $q$ are placed in small columns of the first row. Their horizontal neighbors are consecutive small numbers, and the value below column $c$ is of the form $p+c+1$. In the general case $p\notin\{3,5,7\}$, these values do not introduce a common divisor. This is exactly why the small-prime cases are treated separately.

It remains to check the boundary between the two blocks. In row $r$, the two boundary values are

$$(r+1)p,\quad 5p+(5-r)q.$$

Suppose they have a common prime divisor. If that divisor is $p$, then $p$ must divide $(5-r)q$, which is impossible because $p\neq q$ and . Otherwise, the divisor must divide , so the only possible small primes are . The prime is ruled out by parity, and the cases where or could matter are precisely among the small-prime cases handled separately. Thus the boundary pairs are also coprime in the general case.

Now consider the exceptional cases.

If $2N-1$ is prime, let $q=2N-1$. We use one large block of width $q$ and one small column. Define

$$A_{r,c}= \begin{cases} 6+c+rq & (0\leq c<q),\\ 5-r & (c=q). \end{cases}$$

Then column $q-6$ contains

$$q,\ 2q,\ 3q,\ 4q,\ 5q.$$

Swap $A_{1,q-6}$ with $A_{1,q}$, and swap $A_{3,}$ with . The dangerous column becomes

$$q,\ 4,\ 3q,\ 2,\ 5q,$$

so all vertical pairs in that column are coprime. The only other affected edges are around the small numbers $2,4$ and the moved values $2q,4q$, and they are also coprime by direct checking.

If $p=q$, we use a slightly different right block:

$$A_{r,c}= \begin{cases} 1+c+rp & (0\leq c<p),\\ (8-r)p+c+1 & (p\leq c<2p). \end{cases}$$

The horizontal edges are still mostly automatic, and the only dangerous places are columns containing multiples of $p$. The implementation first swaps the values $7p,9p$ with the small values $7,9$ to separate the dangerous multiples in the right block. Then it fixes the last column of the left block depending on $p\bmod 3$. If , it moves to the first row and places in the last column, as in the general case. Otherwise, it moves to the first row and places in the last column. In both cases, only constantly many edges are affected, and each can be checked directly.

For $p=3,5,7$, the general repair can conflict with small prime divisors. Therefore, the solution uses a precomputed small block of size $5\times p$ containing the numbers $1,2,\cdots,5p$. The large block of width contains the numbers through in a regular pattern. The small block and the boundary are chosen so that they contain only good pairs, and the single dangerous column of multiples of in the large block is fixed by a few swaps. Since these cases occur only for , storing the small patterns directly in the code is sufficient.

Finally, very small values such as $N=1,2,3,5$ are handled by hardcoded grids. For these values, the grid is small enough that the permutation condition and all adjacency conditions can be checked directly.

The algorithm is as follows.

• Read all input values and compute $\max N_i$.
• Use the sieve of Eratosthenes to compute all primes up to $2\max N_i$.
• For each $N_i$, choose the appropriate case above and construct the grid.

The sieve takes $O(M\log\log M)$ time, where $M=2\max N_i$. Printing the grids takes time proportional to the total output size, namely . The memory usage is for the prime table and one constructed grid.

This construction makes every adjacent pair a good pair, so it achieves $B_i=0$ for every test case. Therefore it obtains the maximum possible score.

Solution written by GPT5.5