Sylvester construction

A Hadamard matrix of order $n$ is an $n \times n$ matrix whose entries are only $1$ and $-1$, written $H_n$, satisfying $H_n H_n^T = n I_n$, where $I_n$ is the $n \times n$ identity matrix. A notable property of Hadamard matrices is that they attain the largest possible determinant among all $n \times n$ matrices whose entries lie in $[-1, 1]$. Hadamard matrices are used in error-correcting codes and in weighing designs.

The Sylvester construction builds a Hadamard matrix of size $2n$ from $H_n$:

$H_{2n} = \begin{pmatrix} H_n & H_n \\ H_n & -H_n \end{pmatrix}$

For example,

$H_1 = \begin{pmatrix} 1 \end{pmatrix}, \qquad H_2 = \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}$

and so on.

In this problem you must print a portion of a Hadamard matrix constructed in this way.

The first number in the input is the number of test cases that follow. Each test case consists of five integers $n$, $x$, $y$, $w$, and $h$. $n$ is a power of two with $1 \le n \le 2^{62}$. The pair $(x, y)$ is the upper-left corner of the sub-matrix to print, where $x$ is the column index and $y$ is the row index; $w$ and $h$ are its width and height. Coordinates are zero-based, so $0 \le x, y < n$. The sub-matrix always fits entirely inside the full matrix, and $0 < w, h \le 20$. There are at most $1000$ test cases.

For each test case, print the requested sub-matrix, with the entries in each row separated by single spaces. Print one blank line between the outputs of consecutive test cases.