提示: 欢迎访问OurACM平台。因与高数考试冲突,校赛改为5月6日13:00-17:00
Problem 1071 Early Warning of Tsunami

Accept: 144    Submit: 476
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

The great Tsunami caused by the earthquake of the Indian ocean made the abrupt disaster in the Southeast and the South of Asia on December 26, 2004. In order to avoid the re-happening of the tragedy, China-ASEAN Seminar on the Early Warning of Earthquake and Tsunami was held in Beijing in January 2005. The meeting passed the planning of setting up a tsunami early warning system. The system works by analyzing the information of earthquake wave to forecast the arriving time of the seismic sea waves caused by Tsunami, so that the people can get ready for it to lessen the loss.

Input

The first line of the input is an integer n (0<=n<=100), denoting the number of test cases. The following lines are the data of n test cases. The first line of each test case consists of two integers x and y (0<x<1000, 0<y<1000) separated by one space, denoting the width and height of an earthquake wave figure. The next y lines describe the earthquake wave figure, which is a matrix with elements 0 or 1 (1 denotes the point of the wave) and with one space between every two elements in a line. In the matrix, the points of the wave are continuous, that is each point of the wave is just connected with two adjacent points of the four (up, down, left, right) directions on the wave. But the leftmost point is only connected with its right point and the rightmost point is only connected with its left point. The wave begins at the left side and ends at the right side in the earthquake wave figure. Your task is to calculate the number of the complete peaks of the wave in the earthquake wave figure.

The complete peak of wave is that it consists both of the ascending part in the left side and the descending part in the right side.

Output

For each test case, output an answer (an integer), occupying one line.

Sample Input

2 6 4 0 0 0 0 0 0 0 1 1 1 0 0 0 1 0 1 1 0 1 1 0 0 1 1 10 7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 0 1 1 0 1 1 1 0 1 1 0 0 0 1 1 0 1 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0

Sample Output

1 2

Source

FJNUPC 2005

Submit  Back  Status  Discuss