Luis has a new toy, is a weird board with NxM cells. The cells can be white or
black.
Each cell has a button inside, when you press a button every cell with Manhattan
distance equal or less than K to the cell with the button pressed change of color
( white to black, or black to white ).
At the beginning, every cell is white but somebody pressed some buttons and now
the board has some black cells.
Help Luis to find how many buttons were pressed.
You can assume that no button will be pressed two or more times.
There will be always only one configuration of buttons pressed that generate the
final board.

Input

The first line of input contains an integer t<=10, the number of test cases. It is
followed by t test cases, each consisting of N+1 lines. The first line of each case
contains three integers N,M,K separated by space (1<=N,M<=20 , 0<=K<=20).
The next N lines contains M integers, each integer can be 0 or 1, the final state of
each cell. ( 0 is white, 1 is black )

Output

For each case, output a single line consisting of the number of buttons pressed.

Example

Input:
2
2 2 0
1 0
0 1
2 2 1
1 1
1 1
Output:
2
4