맨하탄 배선

$n \times m$ 칸으로 이루어진 직사각형 격자가 있다. 이 중 정확히 두 칸은 "2", 다른 두 칸은 "3"으로 표시되어 있으며, 일부 칸은 장애물이다.

두 개의 "2" 칸을 하나의 선으로 잇고, 두 개의 "3" 칸을 또 다른 선으로 이으려고 한다. 선은 장애물이 아닌 칸의 중심을 지나며, 상하좌우로 이웃한 두 칸 사이를 가로 또는 세로로만 연결한다.

규칙은 다음과 같다.

• 선은 장애물 칸을 지날 수 없다.
• 한 칸은 최대 하나의 선만 지날 수 있다. 따라서 두 선은 같은 칸을 공유할 수 없고, 서로 교차하지 않는다.
• 선의 길이는 선이 가로지르는 칸 경계의 개수이다. 즉, 경계를 공유하는 이웃한 두 칸을 이은 선의 길이는 $1$이다.

두 선의 길이의 합이 최소가 되도록 할 때, 그 최솟값을 구한다. 두 쌍을 모두 규칙에 맞게 이을 수 없다면 답은 $0$이다.

예를 들어, 아래 첫 번째 예제의 첫 격자에서는 두 쌍을 모두 이었을 때 두 선의 길이의 합을 최소 $18$로 만들 수 있다.

첫째 줄에 데이터 세트의 개수 $T$가 주어진다.

각 데이터 세트의 첫째 줄에는 행의 개수 $n$과 열의 개수 $m$이 주어진다. ($2 \le n \le 9$, $2 \le m \le 9$)

다음 $n$개의 줄에는 격자의 각 행이 위에서 아래로 주어지며, 한 줄에 $m$개의 정수가 공백으로 구분되어 주어진다. 각 정수의 의미는 다음과 같다.

• $0$: 빈 칸
• $1$: 장애물
• $2$: "2"로 표시된 칸
• $3$: "3"으로 표시된 칸

각 격자에는 "2"로 표시된 칸이 정확히 두 개, "3"으로 표시된 칸이 정확히 두 개 있다.

각 데이터 세트마다 두 선의 길이의 합의 최솟값을 한 줄에 하나씩 출력한다. 두 쌍을 모두 이을 수 없으면 $0$을 출력한다.