Problem - 1996B - Codeforces

Codeforces Round 962 (Div. 3)
Finished

→ Virtual participation

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests. If you've seen these problems, a virtual contest is not for you - solve these problems in the archive. If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive. Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

→ Problem tags

greedy

implementation

*800

No tag edit access

Tina has a square grid with $$$n$$$ rows and $$$n$$$ columns. Each cell in the grid is either $$$0$$$ or $$$1$$$.

Tina wants to reduce the grid by a factor of $$$k$$$ ($$$k$$$ is a divisor of $$$n$$$). To do this, Tina splits the grid into $$$k \times k$$$ nonoverlapping blocks of cells such that every cell belongs to exactly one block.

Tina then replaces each block of cells with a single cell equal to the value of the cells in the block. It is guaranteed that every cell in the same block has the same value.

For example, the following demonstration shows a grid being reduced by factor of $$$3$$$.

Original grid

$$$0$$$	$$$0$$$	$$$0$$$	$$$1$$$	$$$1$$$	$$$1$$$
$$$0$$$	$$$0$$$	$$$0$$$	$$$1$$$	$$$1$$$	$$$1$$$
$$$0$$$	$$$0$$$	$$$0$$$	$$$1$$$	$$$1$$$	$$$1$$$
$$$1$$$	$$$1$$$	$$$1$$$	$$$0$$$	$$$0$$$	$$$0$$$
$$$1$$$	$$$1$$$	$$$1$$$	$$$0$$$	$$$0$$$	$$$0$$$
$$$1$$$	$$$1$$$	$$$1$$$	$$$0$$$	$$$0$$$	$$$0$$$

Reduced grid

$$$0$$$	$$$1$$$
$$$1$$$	$$$0$$$

Help Tina reduce the grid by a factor of $$$k$$$.

Input

The first line contains $$$t$$$ ($$$1 \leq t \leq 100$$$) – the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 1000$$$, $$$1 \le k \le n$$$, $$$k$$$ is a divisor of $$$n$$$) — the number of rows and columns of the grid, and the factor that Tina wants to reduce the grid by.

Each of the following $$$n$$$ lines contain $$$n$$$ characters describing the cells of the grid. Each character is either $$$0$$$ or $$$1$$$. It is guaranteed every $$$k$$$ by $$$k$$$ block has the same value.

It is guaranteed the sum of $$$n$$$ over all test cases does not exceed $$$1000$$$.

Output

For each test case, output the grid reduced by a factor of $$$k$$$ on a new line.

Example

Input

Output