미친 수의사

미친 수의사(Mad Veterinarian) 퍼즐에는 여러 대의 기계를 만든 미친 수의사가 등장합니다. 각 기계는 동물 한 마리를 한 마리 이상의 동물로 변신시키며, 모든 기계는 거꾸로도 작동할 수 있습니다. 문제는, 기계들을 정방향 또는 역방향으로 어떤 순서로든 적용하여 어떤 동물 모음을 다른 모음으로 바꿀 수 있는지 판정하는 것입니다. 예를 들면 다음과 같습니다.

• 기계 A는 개미 한 마리를 비버 한 마리로 바꿉니다.
• 기계 B는 비버 한 마리를 개미 한 마리, 비버 한 마리, 쿠거 한 마리로 바꿉니다.
• 기계 C는 쿠거 한 마리를 개미 한 마리와 비버 한 마리로 바꿉니다.

비버 한 마리와 쿠거 한 마리를 개미 3마리로 바꿀 수 있을까요? 가능합니다: {b, c} → (C 적용) → {a, 2b} → (A 역방향 적용) → {2a, b} → (A 역방향 적용) → {3a}. 이 과정은 3단계입니다.

개미 한 마리를 개미 2마리로 바꿀 수 있을까요? 불가능합니다.

이러한 퍼즐은 다음 성질을 가집니다.

1. 정방향에서 각 기계는 특정 종의 동물 한 마리를, 퍼즐에 등장하는 종들로 이루어진 유한하고 비어 있지 않은 모음으로 바꿉니다.
2. 각 기계는 역방향으로도 작동할 수 있습니다.
3. 종마다 기계가 정확히 하나씩 있으며, 그 기계는 정방향에서 해당 종의 동물 한 마리를 입력으로 받습니다.

이 문제에서 모든 퍼즐은 정확히 세 대의 기계 A, B, C를 가지며, 각각 종 a, b, c에 작용합니다. 시작 모음을 목표 모음으로 바꾸는 가장 짧은 기계 적용 순서의 길이를(존재한다면) 구하세요.

첫째 줄에는 정수 P (1 ≤ P ≤ 1000)가 주어지며, 이는 뒤따르는 데이터 집합의 개수입니다. 각 데이터 집합은 서로 동일하고 독립적으로 처리됩니다.

각 데이터 집합은 그 집합에 속한 퍼즐 질문의 개수 N을 담은 줄로 시작합니다. 이어지는 세 줄은 기계 A, B, C를 이 순서대로 설명합니다. 각 기계 줄에는 공백으로 구분된 정수 세 개가 있으며, 입력 동물 한 마리에 대해 그 기계가 출력하는 종 a, b, c의 동물 수를 나타냅니다. 그다음 N개의 줄에는 각각 한 칸 공백으로 구분된 정수 여섯 개가 주어집니다. 앞의 세 개는 동물 a, b, c의 시작 개수이고, 뒤의 세 개는 목표로 하는 a, b, c의 최종 개수입니다.

각 퍼즐 질문마다 한 줄을 출력합니다. 시작 모음에서 목표 모음에 도달할 수 없으면 NO SOLUTION을 출력합니다. 그렇지 않으면 정수 하나를 출력합니다. 이는 목표에 도달하는 데 필요한 최소 기계 적용 횟수이며, 정방향이든 역방향이든 한 번의 적용을 1단계로 셉니다.