SP3477 BABY - Baby

婴儿正在尝试解决知名的八皇后问题：在一个 8×8 的国际象棋棋盘上放置 8 个皇后，要求任何两个皇后不能在同一行、同一列或同一对角线上。婴儿对行和列的概念理解得很清楚，但对角线对她来说还不太明确。所以她成功地将 8 个皇后放在棋盘上，使得没有两个皇后占据相同的行或列，但可能有些皇后在同一对角线上。 现在给你婴儿的皇后摆放位置（她的一个解）以及一个已经给出的正确的八皇后解题方案。问题是要求我们通过移动婴儿的皇后，将它们移动到这个正确的方案中对应皇后的位置。假定在一次移动中，皇后可以向任意一个未被占用的位置进行一格的行或列方向的移动。 请编写一个程序，计算将婴儿的皇后移动到正确解位置所需的最少移动步数。此程序还要适用于一般的 n 皇后问题，问题中 n 个皇后放置在 n×n 的棋盘上。

输入由多组测试用例组成。 每组用例先是一个整数 $n$，表示棋盘的大小以及皇后的数量。 接着的两行各包含 $n$ 个整数。第一行的数字表示婴儿在第 1, 2, ..., $n$ 行时，皇后的列号。相同的规则第二行提供正确解的皇后列号。行与行之间用空格分隔。 输入在一行以 `0` 开头结束。

对于每个测试用例，输出所需的最少移动次数。

棋盘尺寸满足 $4 \le n \le 16$。 **本翻译由 AI 自动生成**