여덟 조각 퍼즐

3행 3열 판에 1부터 8까지 번호가 붙은 정사각형 조각 여덟 개와 빈 칸 하나가 놓여 있다. 한 번의 이동은 빈 칸과 변을 맞댄 조각 하나를 빈 칸으로 밀어 넣는 것이다.

섞인 판이 주어지면 조각을 다음 모양으로 맞추어야 한다.

123
456
78#

여기서 #는 빈 칸이다. 각 판을 목표 모양으로 만드는 최소 이동 횟수를 구하고, 목표 모양을 만들 수 없으면 그 사실을 알리는 프로그램을 작성하시오.

첫째 줄에 테스트 케이스의 개수 $n$이 주어진다. ($1 \le n \le 100$) 그다음에 빈 줄이 하나 온다.

각 테스트 케이스는 시작 판을 나타내는 세 줄로 주어지고, 각 줄은 기호 세 개로 이루어진다. 테스트 케이스 사이에는 빈 줄이 하나씩 들어간다. 한 판에는 기호 1부터 8까지와 #가 정확히 한 번씩 나오며, #는 빈 칸을 뜻한다.

각 테스트 케이스마다 목표 모양을 만드는 최소 이동 횟수를 한 줄에 하나씩 출력한다. 목표 모양을 만들 수 없으면 impossible을 출력한다.