갭 (Gap)

갭(Gap)이라는 카드 게임을 살펴봅시다.

카드는 모두 28장이며, 각 카드에는 두 자리 숫자가 적혀 있습니다. 첫 번째 자리(1부터 4까지)는 카드의 무늬를 나타내고, 두 번째 자리(1부터 7까지)는 카드의 값을 나타냅니다.

카드를 섞은 뒤, 각 줄의 맨 왼쪽에 빈칸을 하나씩 남겨 두고 한 줄에 7장씩 네 줄로 앞면이 보이도록 늘어놓습니다. 아래 그림은 처음 배치의 한 예입니다.

다음으로 값이 1인 카드 네 장을 빼내어 각 줄 왼쪽 끝의 빈칸으로 옮깁니다. "11"은 맨 윗줄로, "21"은 둘째 줄로, "31"은 셋째 줄로, "41"은 맨 아랫줄로 옮깁니다. 카드를 빼낸 자리에는 빈칸이 하나씩 생기는데, 이 빈칸을 갭(gap)이라고 부릅니다.

이제 네 줄 여덟 열에 28장의 카드와 네 개의 갭이 놓이며, 이 배치에서부터 카드를 옮기기 시작합니다.

한 번의 이동에서는 네 개의 갭 중 하나를 골라, 그 갭의 바로 왼쪽에 있는 카드의 다음 카드로 그 갭을 채웁니다. 어떤 카드의 다음 카드란 같은 무늬에서 값이 1 큰 카드를 말합니다. 예를 들어 "42"의 다음 카드는 "43"이고, "27"에는 다음 카드가 없습니다. 위 배치에서는 "43"을 "42"의 오른쪽 갭으로 옮기거나 "36"을 "35"의 오른쪽 갭으로 옮길 수 있습니다. "43"을 옮기면 원래 "43"이 있던 자리("16"의 오른쪽)에 새로운 갭이 생깁니다. 값이 7인 카드의 오른쪽에 있는 갭이나, 다른 갭의 오른쪽에 있는 갭은 채울 수 없습니다.

이동을 잘 선택하여, 아래처럼 각 줄이 같은 무늬의 오름차순 수열이 되도록 만드는 것이 목표입니다.

주어진 배치에서 목표 배치에 도달하기 위한 최소 이동 횟수를 구하세요.

첫째 줄에는 뒤이어 주어지는 배치의 개수가 주어집니다.

각 배치는 다섯 줄로 주어집니다. 먼저 빈 줄 하나가 오고, 이어서 네 줄이 각 줄의 배치를 나타냅니다. 이 네 줄 각각에는 한 줄에 놓인 카드 7장이 왼쪽에서 오른쪽 순서로, 두 자리 숫자로 주어집니다.

각 배치마다 목표 배치에 도달하기 위한 최소 이동 횟수를 한 줄에 출력합니다. 이 횟수에는 값이 1인 카드를 제자리로 옮기는 처음 네 번의 이동을 포함하지 않습니다. 주어진 배치에서 목표 배치에 도달할 수 없으면 -1을 출력합니다.