一名刚从捷克理工大学毕业的土木工程师遇到了一个有趣的问题，并向我们寻求帮助。这个问题与其说是工程问题，不如说是经济问题。该工程师需要用基础设施将几栋建筑物连接起来。不幸的是，投资者并不拥有这些地点之间的所有土地。因此，必须先购买一些地块。

土地被划分为规则的六角形地块“网格”，每个地块都是一个独立的单元，且价值相同。部分地块属于投资者。这些地块形成了四个连通区域，每个区域包含一栋需要与其他建筑物连接的建筑物。您的任务是找到必须购买的最少地块数量，以将这四个给定的区域连接起来。

整个土地也呈六角形，有六条边，每条边恰好由 $H$ 个地块组成。上图显示了 $H = 4$ 的土地，带有字母的地块代表要连接的四个区域。在这种情况下，需要购买四个额外的地块。其中一种可能的解决方案用叉号（$\times$）表示。

输入格式

输入包含多个测试用例。每个测试用例以一个整数 $H$ 开始，表示土地的大小，$2 \le H \le 20$。接下来有 $2H - 1$ 行，表示土地的各个“行”（其方向始终与图中一致）。这些行中每个地块包含一个非空格字符。这意味着第一行将包含 $H$ 个字符，第二行包含 $H + 1$ 个字符，依此类推。最长的一行将是中间那行，包含 $2H - 1$ 个字符。然后“长度”依次递减，最后一行再次包含 $H$ 个地块。

代表地块的字符要么是点号（.），表示不属于投资者的土地；要么是大写字母 A、B、C 或 D 之一。被相同字母占用的地块区域总是连通的。这意味着在同一区域的任意两个地块之间，存在一条仅通过该区域的路径。

除了代表地块的字符外，行中可以在任何位置包含任意数量的空格，以提高输入的可读性。两个字母（或点号）之间至少有一个空格。在土地描述之后，会有一个空行，然后开始下一个测试用例。最后一个测试用例后面紧跟一行，内容为 0。

输出格式

对于每个测试用例，输出一行，格式为 You have to buy P parcels.，其中 $P$ 是为了使所有四个区域连接在一起而必须购买的最少地块数量。

如果可以在区域之间找到一条仅通过已购买地块的路径，则认为这些区域是连通的。

样例

输入样例 1

4
     B . . C
    . . . . C
   . A . . C .
  . A A . . . .
   . A . . . .
    . . . D D
     . . . .

0

输出样例 1

You have to buy 4 parcels.