맨하탄 배선

n * m 칸으로 이루어진 직사각형 영역이 있다. 이 중, 두 칸은 "2"로 표시되어 있고, 다른 두 칸은 "3"으로 표시되어 있다. 어떤 칸에는 장애물이 있다. 이때, 두 "2"와 두 "3"을 교차하지 않는 선분으로 이으려고 한다. 선은 장애물이 아닌 칸의 중심을 가로 또는 세로로 연결할 수 있다.

한 칸에는 최대 1개의 선만 있을 수 있고, 선이 서로 교차할수는 없다. 이때, 두 선의 길이의 합이 최소가 되는 것을 찾으려고 한다. 선의 길이는 선이 통과하는 칸의 경계의 개수이다. 즉, 경계를 공유하는 두 칸을 이은 선의 길이는 1이다.

아래 그림 (a)는 영역의 예시이고, (b)는 위의 조건을 만족하게 선을 그린 것이고, 길이는 18이다.

입력은 여러 개의 데이터 세트로 이루어져 있다. 첫째 줄에는 데이터 세트의 개수 T가 주어진다. 다음 줄부터는 각각의 데이터 세트의 정보가 주어지며, 다음과 같이 구성되어져 있다.

첫째 줄에는 행의 개수 n과 열의 개수 m이 주어진다. (2 ≤ n ≤ 9, 2 ≤ m ≤ 9) 다음 줄부터 n개의 줄에는 1행의 정보부터 n행의 정보가 한 줄에 하나식 주어지며, m개의 숫자가 공백으로 구분되어 있다. 숫자의 의미는 다음과 같다.

0: 빈 칸

1: 장애물

2: "2"로 표시된 곳

3: "3"으로 표시된 곳

각각의 데이터 세트에 대해서, 문제의 조건을 만족하는 두 선의 길이의 최솟값을 출력한다. 만약, 조건을 만족하는 선을 그릴 수 없다면 "0"을 출력한다.