육각형 필지

한 토목 기술자가 여러 건물을 기반 시설로 연결하려고 합니다. 투자자는 건물들 사이의 모든 땅을 소유하고 있지 않으므로, 일부 필지를 먼저 사들여야 합니다.

땅은 육각형 필지들이 규칙적인 격자를 이루도록 나뉘어 있습니다. 각 필지는 독립된 단위이며 모두 같은 가치를 가집니다. 일부 필지는 이미 투자자의 소유이며, 이들은 네 개의 연결된 구역을 이룹니다. 각 구역에는 서로 연결되어야 하는 건물이 하나씩 있습니다. 네 구역이 모두 연결되도록 추가로 사들여야 하는 필지의 최소 개수를 구하세요.

전체 땅도 육각형 모양이며, 여섯 변은 각각 정확히 H개의 필지로 이루어져 있습니다. 각 필지는 비어 있는 땅을 뜻하는 점(.)이거나, 투자자가 소유하며 자신이 속한 구역을 나타내는 대문자 A, B, C, D 중 하나로 표시됩니다. 같은 글자를 가진 필지들은 항상 하나의 연결된 구역을 이룹니다. 예를 들어 H = 4이고 첫 번째 예제처럼 구역이 배치되어 있으면, 네 구역을 모두 연결하는 데 추가 필지 네 개면 충분합니다.

입력은 여러 개의 시나리오로 이루어집니다. 각 시나리오는 땅의 크기를 나타내는 정수 H(2 ≤ H ≤ 20)가 적힌 한 줄로 시작합니다. 그 뒤로 육각형의 각 행을 나타내는 2·H − 1개의 줄이 이어집니다. 첫 줄에는 H개, 둘째 줄에는 H + 1개의 필지가 있고, 이런 식으로 늘어나 가운데 줄에서 2·H − 1개가 되며, 그 뒤로 다시 줄어들어 마지막 줄에서 H개가 됩니다.

각 필지는 공백이 아닌 한 글자로 표기됩니다. 비어 있는 땅은 점(.), 소유된 땅은 A, B, C, D 중 하나입니다. 가독성을 위해 각 줄에는 임의의 위치에 공백이 얼마든지 들어갈 수 있지만, 두 필지 글자 사이에는 항상 최소한 하나의 공백이 있습니다. 각 땅 설명 뒤에는 빈 줄이 하나 있습니다. 마지막 시나리오 다음에는 0 하나만 적힌 줄이 오며, 이 줄은 처리하지 않습니다.

각 시나리오마다 다음 형식의 한 줄을 정확히 출력하세요.

You have to buy P parcels.

여기서 P는 네 구역이 모두 연결되도록 사들여야 하는 필지의 최소 개수입니다. 두 구역은 투자자가 소유했거나 사들인 필지만을 지나는 경로로 이어질 수 있을 때 연결된 것으로 봅니다. 사들이지 않은 빈 필지는 장애물 역할을 합니다.