Leo has a grid with `N` × `N` cells. He wants to paint each cell either black or white.

After he finished painting, the grid will be divided into several parts. Any two connected cells should be in the same part, and any two unconnected cells should be in different parts. Two cells are connected if they share an edge and they are in the same color. If two cells are connected with the same another cell, the two cells are also connected.

The size of a part is the number of cells in it. Leo wants to have at least ⌊`N×4÷3`⌋ different sizes (⌊`x`⌋ is the maximum integer which is less than or equal to `x`).

Can you tell him how to paint the grid?

There are multiple test cases. The first line of input is an integer `T` indicates the number of test cases. For each test case:

There is one integer `N` (4 <= `N` <= 100).

提交代码