BTTNS - Buttons

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

Added by:Paulo Costa
Date:2012-01-30
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:UGTO

hide comments
2017-12-21 00:09:56 Antonio Roberto Paoli
Just curiosity: How can we know the number of test cases if we donĀ“t have access to then?

Last edit: 2018-02-14 23:57:15
2017-08-23 20:57:18 Thotsaphon Thanatipanonda
number of test cases is 100 not <= 10
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.