CF1520C Not Adjacent Matrix

We will consider the numbers $ a $ and $ b $ as adjacent if they differ by exactly one, that is, $ |a-b|=1 $ . We will consider cells of a square matrix $ n \times n $ as adjacent if they have a common side, that is, for cell $ (r, c) $ cells $ (r, c-1) $ , $ (r, c+1) $ , $ (r-1, c) $ and $ (r+1, c) $ are adjacent to it. For a given number $ n $ , construct a square matrix $ n \times n $ such that: - Each integer from $ 1 $ to $ n^2 $ occurs in this matrix exactly once; - If $ (r_1, c_1) $ and $ (r_2, c_2) $ are adjacent cells, then the numbers written in them must not be adjacent.

The first line contains one integer $ t $ ( $ 1 \le t \le 100 $ ). Then $ t $ test cases follow. Each test case is characterized by one integer $ n $ ( $ 1 \le n \le 100 $ ).

For each test case, output: - -1, if the required matrix does not exist; - the required matrix, otherwise (any such matrix if many of them exist). The matrix should be outputted as $ n $ lines, where each line contains $ n $ integers.