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