题号：NC210601
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld
题目描述
You a given a board with 
cells. You want to color some cells black such that
- Black cells may never be orthogonally connected (they may not share a side, although they can touch diagonally).
- All white cells must be interconnected.
Find a configuration with the maximum number of black cells.
- Black cells may never be orthogonally connected (they may not share a side, although they can touch diagonally).
- All white cells must be interconnected.
Find a configuration with the maximum number of black cells.
输入描述:
The first line contains one integer— the number of test cases.
For each test cases, the first line contains one integer.
输出描述:
For each test cases, output n binary strings with length n in n lines representing the board. `1` indicates a black cell, and `0` indicates a white cell.