SP5163 VIENTIAN - Tower of Vientiane

汉诺塔是一种经典的数学游戏或谜题，由三根柱子和若干个可以滑动的不同大小的圆盘组成。游戏开始时，圆盘按大小顺序整齐地堆放在一根柱子上，最小的圆盘位于最上方，形成一个锥形结构。游戏的目标是将所有圆盘移动到另一根柱子上，并遵循以下规则： - 每次只能移动一个圆盘。 - 每次移动时，仅能从某一柱子的顶部取下一个圆盘，并将其放到另一根柱子的顶部，该柱子上可能已经有其他圆盘。 - 任何时候都不能将较大的圆盘放在较小的圆盘上。 我们知道，对于 $n$ 个圆盘的汉诺塔问题，最少需要 $2^n - 1$ 步才能解决。 现在，让我们来看一下另一个称为“万象塔”的谜题。这个谜题与汉诺塔类似，但增加了一些移动限制。假设初始柱子编号为 1，目标柱子编号为 3，辅助柱子编号为 2。题目会给出一个矩阵，指示哪些移动是允许的。例如，可能规定只允许从柱子 1 移动到柱子 2，从柱子 2 移动到柱子 3，以及从柱子 3 移动到柱子 1。你的任务是在给定的移动限制下，找出解决这个谜题的最少步数。

输入的第一行包含一个整数 $t$，表示有多少组测试用例。接下来是 $t$ 组测试数据。每组测试数据首先包括一个 $3 \times 3$ 的矩阵，矩阵中的元素为 1 或 0。位于第 $i$ 行第 $j$ 列的 1 表示可以从柱子 $i$ 移动到柱子 $j$，否则不能。每组测试数据的下一行给出一个整数 $n$，表示这一组数据中的圆盘数量。

对于每组测试数据，输出解谜所需的最少步数。如果在给定的限制条件下无法完成谜题，则输出 "Epic Fail..."。 **本翻译由 AI 自动生成**