Ski Lifts

Climate change has turned the rolling mountains of Alaska into a perfect place for all-season skiing. To transform this region into a successful skiing area, however, ski lifts are needed. People who ski do not like walking uphill. They want to ski downhill; when needed they are willing to ski on the same level for a while.

Optimal use of the area requires that, starting from an arbitrary point, a skier be able to reach any other point just by skiing downhill or staying on the same level, and occasionally taking a ski lift.

A sufficient number of ski lifts must be planned and constructed to fulfill this condition. On the other hand, building more ski lifts than necessary is a waste of money.

What is the minimum number of ski lifts needed?

Because ski lifts are built on high poles, we assume a ski lift can be constructed from any point to any other point, regardless of the terrain in between. A ski lift is unidirectional.

Note that in Alaska one may only ski in the four directions North, South, East, or West. In other words a skier may only move to a 4-directionally adjacent cell, and may ski there only when that cell's height is lower than or equal to the current cell's height.

The first line of the input contains a single integer: the number of test cases that follow. Each test case has the following format:

• A line with two integers $w$ and $l$ ($1 \le w, l \le 500$): the width and length of the area.
• $w$ lines follow, each containing $l$ integers $h_{ij}$ ($0 \le h_{ij} \le 10^9$), representing the height at each point of the area.

For every test case, output a single integer on its own line: the minimum number of ski lifts to be built.