Time Limit: 1000 MS    Memory Limit: 131072 K 


Description

Long time ago, a king occupied a vast territory. Now there is a problem that he worried that he did not know how much of the perimeter of his territory. Can you help him? For simplicity, we use a matrix to represent the territory as follows: 0 0 0 0 0 0 1 0 1 0 1 1 0 1 0 0 1 1 0 0 0 0 1 0 0 Every single number in the matrix represents a piece of land, which is a 1*1 square 1 represents that this land has been occupied 0 represents not Obviously the perimeter of all ocupied lands is 20

Input

The first line of the input contains a single integer t (1t5) the number of cases. For each case The first line has two integers N and M representing the length and width of the matrix Then M lines follows to describe the matrix 1N,M400

Output

For each case output the perimeter of all ocupied lands

Sample Input

1 5 5 0 0 0 0 0 0 1 0 1 0 1 1 0 1 0 0 1 1 0 0 0 0 1 0 0

Sample Output

20