作为学习动态规划的入门，数字三角形问题是非常经典的。在这里，我们将重温这个经典问题。

通过从下方三角形的任意位置出发，向上移动到相邻的数字，从底到顶的最大总和为 23。

$$ \begin{matrix} & & & 3 & & & \\ & & 7 & & 4 & & \\ & 2 & & 4 & & 6 & \\ 8 & & 5 & & 9 & & 3 \end{matrix} $$

然而，仅仅求出最大总和是不够的。同样地，我们关注路径。考虑下面的新三角形以及对应的字母三角形。从底到顶的最大总和为 6，经过了两个 “2”。

$$ \begin{matrix} & & & 2 & & & \\ & & 1 & & 1 & & \\ & 2 & & 1 & & 1 & \\ 1 & & 1 & & 2 & & 1 \end{matrix} $$

$$ \begin{matrix} & & & a & & & \\ & & a & & b & \\ & b & & a & & a & \\ b & & a & & b & & a \end{matrix} $$

一条最优路径可以通过将路径上对应的字母依次连接成一个字符串来表示。 那么在上面的三角形中，从最后一行第一个位置出发的字典序最小的最优路径是 “bbaa”。 从最后一行第二个位置出发的字典序最小的最优路径是 “abaa”。 从最后一行第三个位置出发的字典序最小的最优路径是 “baaa”。 没有最优路径从最后一行第四个位置出发。

现在，程序需要确定最后一行中哪些位置至少引导出一条最优路径（即从该位置出发存在一条最优路径）。请根据这些位置各自引导出的字典序最小的最优路径的字典序，对这些位置进行排序。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 36$)，表示有 $T$ 组测试数据。 对于每组测试数据，第一行包含一个整数 $N$ ($N \le 1500$)。接下来的 $N$ 行中，第 $i$ 行描述了三角形的第 $i$ 行，包含 $i$ 对整数和字母。输入中的所有整数均为正数且小于 10。

输出格式

对于每个查询，输出一行数字，表示排序后的可能位置列表。如果两个位置拥有相同的字典序最小的最优路径，则优先输出索引较小的位置。

样例

输入 1

3
4
3 e
7 v 4 a
2 a 4 o 6 t
8 w 5 f 9 l 3 p
4
2 a
1 a 1 b
2 b 1 a 1 a
1 b 1 a 2 b 2 a
4
2 a
1 a 1 b
2 b 1 a 1 a
1 b 1 a 2 b 1 a

输出 1

3
4 2 3 1
2 3 1