H. Hot Cappuccino
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Eddard's secret partner likes matrices, so they went on a trip to The Matrix City, which is famous for its coffee shops that make the best cappuccino and hot chocolate. While walking around the city, however, they lost each other. Can you help them meet again?

The city consists of $$$n*m$$$ blocks, each block $$$(x, y)$$$ with a coffee shop that serves cappuccino, hot chocolate, both, or neither.

Initially, Eddard is at block $$$(1, 1)$$$ while his partner is at $$$(n, m)$$$. Each of them can move in the four directions. Since it's already summer and the weather is absolutely terrible, walking is tiresome and each step costs $$$1$$$ willpower.

There is, however, something that can save some willpower for them...

Eddard likes hot chocolate, and his partner likes cappuccino. If they're currently at a block with a coffee shop that serves their preferred drink, they can drink and move to any adjacent block without spending willpower.

Find the minimum sum of willpower spent by both so that they can meet at any block.

Input

The first line of input consists of one integer $$$T (1 \le T \le 10^4)$$$ – The number of test cases.

The first line of each test case consists of 2 integers $$$n, m(1\le n, m \le 10^6, n \cdot m \le 10^6)$$$

The $$$i$$$-th line of the next $$$n$$$ lines consists of $$$m$$$ integers $$$a_{i, 1}, a_{i, 2},...,a_{i, m}$$$, where $$$a_{i,j}$$$ describes the drinks served at the coffee shop in block $$$(i, j)$$$:

  • $$$0$$$ for neither cappuccino nor hot chocolate
  • $$$1$$$ for cappuccino
  • $$$2$$$ for hot chocolate
  • $$$3$$$ for both

It is guaranteed that the sum of $$$n \cdot m$$$ over all test cases will not exceed $$$10^6$$$

Output

Print the answer for each test case on a single line.

Example
Input
4
4 6
2 2 0 0 0 0
0 2 0 0 0 0
0 0 0 0 1 0
0 0 0 0 1 1
10 2
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
3 3
3 3 3
3 3 3
3 3 3
1 1
0
Output
2
10
0
0
Note

In the first test case:

Eddard can move as follows: $$$(1, 1) \gt ^0 (1, 2) \gt ^0 (2, 2) \gt ^0 (2, 3) \gt ^1 (3, 3)$$$

His partner can move as follows: $$$(4, 6) \gt ^0 (4, 5) \gt ^0 (3, 5) \gt ^0 (3, 4) \gt ^1 (3, 3)$$$