Scale

ID: 10710

Type: RemoteJudge

2000ms

256MiB

Tried: 0

Accepted: 0

Difficulty: (None)

Uploaded By:

Hydro

Tags>

greedy

implementation

Description

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$ .

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$ .

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

Input

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

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.

Sample Input 1

Sample Output 1

#P1996B. Scale

Description

Input

Output

Status

Development

Support

$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$

$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$

#P1996B. Scale

Scale

Description

Input

Output

Sample Input 1

Sample Output 1

Status

Development

Support

Don't have an account?

SIGN IN

$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$