题目描述

Hi-Q 是一种流行的单人游戏，游戏盒内包含一个十字形的小孔棋盘和32枚可插入孔中的小棋子。游戏开始时中心孔为空，玩家通过水平或垂直方向跳过一枚棋子来移动棋子，被跳过的棋子将被移除。不允许斜向跳跃。玩家的目标是尽可能多地移除棋盘上的棋子。本题要求编写一个自动玩Hi-Q的程序，研究不同初始棋子布局下游戏的进行情况。

棋盘形状如下，孔编号为$1$至$33$：

                              1         2         3
                              4         5         6
          7         8         9        10        11        12        13
         14        15        16        17        18        19        20
         21        22        23        24        25        26        27        
                             28        29        30
                             31        32        33

游戏开始时，某些孔中有棋子，其他孔为空。游戏通过水平或垂直跳跃进行：若目标孔为空且跳过一枚棋子，则移动棋子至目标孔并移除被跳过的棋子。例如，若$9$为空且$10$和$11$有棋子，则$11$的棋子可移动到$9$，并移除$10$的棋子。此后$10$和$11$为空，$9$有棋子。

给定特定棋盘布局，程序需反复选择并模拟移动，直到无移动可行为止，最后输出剩余棋子所在孔的编号之和。若存在多个可选移动，则选择目标孔编号最大的移动；若目标孔相同，则选择源孔编号较大的移动。

示例：若棋盘状态如下（$X$表示棋子，$O$表示空孔）：

                              O         O         O
                              O         O         O
          O         O         O         X         O         X         O
          O         O         O         X         O         X         O
          O         O         O         O         X         O         O
                              O         O         O
                              O         O         O

则跳跃顺序为：
1. 从$12$跳过$19$到$26$（可选目标为$26$、$24$和$5$，$26$最大）
2. 从$26$跳过$25$到$24$（可选目标为$5$和$24$，$24$更大；$24$为目标时有$26$和$10$两个源，选择$26$）
3. 从$17$跳到$29$（$29 > 5$）
最终剩余$10$和$29$两枚棋子，输出$39$。

注：实际第二跳应为$25$跳过$26$到$27$，第三跳为$10$跳过$17$到$24$，最终剩余$24$和$27$，输出$51$。

输入格式

第一行包含整数$N$（$1 \leq N \leq 10$），表示游戏实例数。后续每行描述一个游戏实例，列出初始有棋子的孔编号（升序排列），以$0$结束。

输出格式

输出共$N+2$行。首行为"HI Q OUTPUT"，随后每行输出一个实例的剩余棋子编号之和，末行为"END OF OUTPUT"。

样例输入

4
10 12 17 19 25 0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
16 17 18 19 20
21 22 23 24 25 26 27 28 29 30 31 32 33 0
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 18 19 20
21 22 23 24 25 26 27 28 29 30 31 32 33 0

样例输出

HI Q OUTPUT
51 
0
561 
98
END OF OUTPUT

来源

Mid-Atlantic 1996