Hive

A field of pink flowers is divided into $N$ rows and $M$ columns of one square meter cells. The cell in row $i$ from the top and column $j$ from the left holds $a_{ij}$ flowers.

Every morning a group of rabbits comes to eat the flowers so that their fur turns pink. A rabbit starts at the top left cell and travels to the bottom right cell, moving one cell right or one cell down at a time. It never goes back to the left and never goes back up. Whenever a rabbit enters a cell that still holds at least one flower, it picks exactly one flower there. It walks past a cell with no flowers left without picking anything.

You may choose the route of every rabbit. Find the smallest number of rabbits needed to pick every flower in the field.

The first line contains the number of test cases $T$ ($1 \le T \le 10$).

The first line of each test case contains the number of rows and columns of the field, $N$ and $M$ ($1 < N, M \le 1600$).

Each of the next $N$ lines contains $M$ integers. The $j$-th integer on the $i$-th line is $a_{ij}$ ($0 \le a_{ij} \le 100$).

For each test case, print the smallest number of rabbits needed to pick every flower, one answer per line.