PushPush

A treasure hunter obtained a map of an ancient pyramid that enshrines a sacred treasure, and set out to recover it. The moment he reached the pyramid's gate an earthquake struck, and some rocks fell from the ceiling to the floor inside the pyramid. Two of those rocks now block the way to the treasure. The rocks are far too large and heavy to pull, so the only thing he can do is push a single rock one block forward. He wants to reach the treasure, pushing rocks aside when necessary. If he ever pushes a rock in the wrong direction and can no longer advance, he must give up the treasure.

In the map of Figure 1, white blocks are open paths and black blocks are barriers. Black circles are rocks, and E and T mark the positions of the entrance and the treasure. A person and the rocks can move north, east, west, or south. To push a rock, the block in front of it and the block behind it (along the push direction) must both be open (white). In Figure 1 the person at E can push the rock at (2, 3) north or east, but not west or south, because he cannot reach positions (2, 4) and (1, 3). If he pushes it east, he cannot push it east a second time, because he cannot push two rocks at once. If he pushes the rock at (2, 5) north, the treasure is destroyed. To obtain the treasure he must push the rock at (2, 3) north and then push the rock at (2, 5) east. Note that no rock can be pushed outside the pyramid.

Figure 1

Figure 2

A map is represented by a matrix, as in Figure 2. In the matrix, 0, 1, 2, 3, and 4 represent an open path, a barrier, the entrance, the treasure, and a rock, respectively. The entrance, the treasure, and the rocks all sit on open paths.

Write a program that computes the minimum number of rock pushes needed to reach the treasure. For the example in Figure 1 the answer is 2. If a path to the treasure exists without pushing any rock, the answer is 0. If no such path exists, the answer is -1.

The input is read from standard input. The first line contains the number of test cases $T$. Each test case begins with a line containing two integers $n$ and $m$, the number of rows and columns of the map ($2 \le n, m \le 50$). Each of the next $n$ lines contains $m$ integers, each 0, 1, 2, 3, or 4, describing one row of the map, where 0, 1, 2, 3, and 4 are an open path, a barrier, the entrance, the treasure, and a rock. Every map contains exactly one 2, exactly one 3, and exactly two 4's. The integers on a line are separated by single spaces.

Write to standard output. For each test case print exactly one line: the minimum number of rock pushes needed to reach the treasure, or -1 if the treasure cannot be reached.