SP9820 WPC4F - Through the troops

马里奥越过了第一个障碍，来到了一个长而狭窄的小巷，这里有许多乌龟。他必须通过在乌龟间跳跃才能穿过小巷。每当他跳到一只乌龟上时，可以选择让这只乌龟处于以下三种状态中的任意一种： - 活跃 (A) - 休眠 (D) - 受伤 (B) 小巷里共有 $n$ 只乌龟，编号从 $0$ 到 $n-1$。每次跳跃会消耗一些能量，这取决于当前乌龟的编号和它所处的状态。但需要注意的是，相邻的乌龟不能处于同样的状态，否则会聚集起来对马里奥发动致命攻击。 乌龟 $i$ 的邻居是乌龟 $i-1$ 和 $i+1$。（**注：** 如果 $n \ge 3$，）首尾两只乌龟不算作邻居。 你的任务是计算出马里奥穿越小巷所需的最小能量。

第一行输入一个整数 $T$，表示测试用例的数量（$T \le 5$）。接下来是 $T$ 组输入数据，每组数据格式如下： - 第一行是一个整数 $n$，表示乌龟的数量（$n \le 20$）。 - 接下来的 $n$ 行中，每行包含三个整数 $a_1, a_2, a_3$，分别表示将第 $i$ 只乌龟状态切换为 A、D、B 所需的能量（$0 \le a_i \le 1000$）。

对于每个测试用例，输出一行，表示穿越小巷所需的最小能量。 **本翻译由 AI 自动生成**