돌 밀기

한 보물 사냥꾼이 신성한 보물이 모셔진 고대 피라미드의 지도를 손에 넣고 보물을 찾아 길을 떠났다. 그가 피라미드 입구에 다다른 순간 지진이 일어나, 피라미드 안쪽의 천장에서 바닥으로 돌 몇 개가 떨어졌다. 그 가운데 두 개의 돌이 보물로 가는 길을 막아 버렸다. 돌은 너무 크고 무거워 끌어당길 수 없고, 할 수 있는 일이라고는 돌 하나를 한 칸 앞으로 미는 것뿐이다. 그는 필요할 때 돌을 밀어내며 보물에 도달하려 한다. 만약 돌을 잘못된 방향으로 밀어 더 이상 나아갈 수 없게 되면 보물을 포기해야 한다.

그림 1의 지도에서 흰 칸은 열린 길, 검은 칸은 장애물이다. 검은 원은 돌이고, E와 T는 각각 입구와 보물의 위치를 나타낸다. 사람과 돌은 북, 동, 서, 남 네 방향으로 움직일 수 있다. 돌을 밀려면 미는 방향을 기준으로 돌의 앞칸과 뒤칸이 모두 열린 길(흰 칸)이어야 한다. 그림 1에서 E에 있는 사람은 (2, 3)에 있는 돌을 북쪽이나 동쪽으로 밀 수 있지만, 서쪽과 남쪽으로는 밀 수 없다. (2, 4)와 (1, 3) 위치로는 사람이 갈 수 없기 때문이다. 그 돌을 동쪽으로 밀면 다음번에 다시 동쪽으로는 밀 수 없는데, 돌 두 개를 한꺼번에 밀 수는 없기 때문이다. (2, 5)에 있는 돌을 북쪽으로 밀면 보물이 부서진다. 보물을 얻으려면 (2, 3)의 돌을 북쪽으로 민 다음 (2, 5)의 돌을 동쪽으로 밀어야 한다. 어떤 돌도 피라미드 바깥으로는 밀어낼 수 없다는 점에 유의하라.

그림 1

그림 2

지도는 그림 2처럼 행렬로 표현된다. 행렬에서 0, 1, 2, 3, 4는 각각 열린 길, 장애물, 입구, 보물, 돌을 나타낸다. 입구와 보물, 돌은 모두 열린 길 위에 놓여 있다.

보물에 도달하기 위해 돌을 미는 최소 횟수를 구하는 프로그램을 작성하라. 그림 1의 예에서 답은 2이다. 돌을 하나도 밀지 않고 보물에 도달하는 길이 있으면 답은 0이다. 그런 길이 존재하지 않으면 답은 -1이다.

입력은 표준 입력으로 주어진다. 첫째 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스의 첫째 줄에는 지도의 행 수 $n$과 열 수 $m$이 주어진다 ($2 \le n, m \le 50$). 이어지는 $n$개의 줄에는 각각 $m$개의 정수가 주어지며, 각 정수는 0, 1, 2, 3, 4 중 하나로 지도의 한 행을 나타낸다. 여기서 0, 1, 2, 3, 4는 각각 열린 길, 장애물, 입구, 보물, 돌이다. 각 지도에는 2가 정확히 하나, 3이 정확히 하나, 4가 정확히 두 개 있다. 한 줄의 정수들은 공백 하나로 구분된다.

각 테스트 케이스마다 표준 출력으로 정확히 한 줄을 출력한다. 보물에 도달할 수 있으면 돌을 미는 최소 횟수를, 도달할 수 없으면 -1을 출력한다.