To improve her intelligence, ZJY has started studying combinatorics. One day, she solved the following problem: "Given a grid where some cells contain treasure, starting from the top-left corner and only moving right or down, what is the minimum number of paths required to collect all the treasure?" However, she was not satisfied and thought of a variation: suppose each cell contains multiple pieces of treasure, and each time you pass through a cell, you can collect at most one piece of treasure. With the other conditions remaining the same, what is the minimum number of paths required to collect all the treasure?

She cannot solve this one; can you help her?

Input

The first line contains a positive integer $t$, representing the number of test cases.

For each test case, the first line contains two positive integers $n$ and $m$, representing that the grid has $n$ rows and $m$ columns.

The next $n$ lines each contain $m$ non-negative integers, representing the amount of treasure in each cell ($0$ means no treasure).

Output

For each test case, output a single integer representing the minimum number of paths required.

Constraints

• For 30% of the data, $n \le 5, m \le 5$, and the number of treasures in each cell does not exceed 5.
• For 50% of the data, $n \le 100, m \le 100$, and the number of treasures in each cell does not exceed 1000.
• For 100% of the data, $n \le 1000, m \le 1000$, and the number of treasures in each cell does not exceed $10^6$.

Examples

Input 1

1
3 3
0 1 5
5 0 0
1 0 0

Output 1

10