Almost Ternary Matrix solution codeforces

Almost Ternary Matrix solution codeforces-

You are given two even integers 𝑛n and 𝑚m. Your task is to find any binary matrix 𝑎a with 𝑛n rows and 𝑚m columns where every cell (𝑖,𝑗)(i,j) has exactly two neighbours with a different value than 𝑎𝑖,𝑗ai,j.

Two cells in the matrix are considered neighbours if and only if they share a side. More formally, the neighbours of cell (𝑥,𝑦)(x,y) are: (𝑥1,𝑦)(x−1,y)(𝑥,𝑦+1)(x,y+1)(𝑥+1,𝑦)(x+1,y) and (𝑥,𝑦1)(x,y−1).

It can be proven that under the given constraints, an answer always exists.

Input

Each test contains multiple test cases. The first line of input contains a single integer 𝑡t (1𝑡1001≤t≤100) — the number of test cases. The following lines contain the descriptions of the test cases.

The only line of each test case contains two even integers 𝑛n and 𝑚m (2𝑛,𝑚502≤n,m≤50) — the height and width of the binary matrix, respectively.

Output

For each test case, print 𝑛n lines, each of which contains 𝑚m numbers, equal to 00 or 11 — any binary matrix which satisfies the constraints described in the statement.

It can be proven that under the given constraints, an answer always exists.

Example

input

Copy
3
2 4
2 2
4 4


output

Copy
1 0 0 1
0 1 1 0
1 0
0 1
1 0 1 0
0 0 1 1
1 1 0 0
0 1 0 1
Note

White means 00, black means 11.

 The binary matrix from the first test case The binary matrix from the second test case The binary matrix from the third test case