这是一个“运行两次”的问题：你的程序将在每个测试点上运行两次。请参阅题目描述的其余部分和输入格式部分以获取更多详细信息。

一个方阵如果是“好的”（good），当且仅当它的行列式为奇数。

一个 $n \times n$ 的二进制矩阵如果是“幸运的”（lucky），当且仅当下面描述的贪心匹配算法成功找到一个大小为 $n$ 的匹配。该算法逐行读取矩阵，从上到下。在每一行中，如果存在一列之前从未被选中过且该位置为 1，算法会贪心地选择最左侧的这样一列。

你的任务是比较 $n \times n$ 的“好的”矩阵和“幸运的”矩阵的数量。为了做到这一点，你需要建立较小集合与较大集合中等势子集之间的一个双射。

输入格式

在每次运行中，第一行包含一个整数 $t$：测试用例的数量。接下来是各个测试用例。 每个测试用例的第一行包含一个字符串 “good” 或 “lucky”，表示矩阵的类型。 下一行包含一个整数 $n$ ($1 \le n \le 2000$)：矩阵的大小。 接下来是 $n$ 行：第 $i$ 行包含一个长度恰好为 $n$ 的二进制字符串，表示矩阵的第 $i$ 行。

在第二次运行中，给你的程序提供的矩阵与你在第一次运行中输出的矩阵完全相同，且顺序一致。

保证所有测试用例中 $n$ 的总和不超过 $2000$。

输出格式

在每次运行中，你必须打印 $t$ 个答案。每个答案要么是一个单独打印在独立行上的整数 $-1$，要么是一个与输入格式类似的、相反类型的矩阵：一行包含大小 $n$，随后是描述矩阵行的 $n$ 行内容。

你的程序所产生的映射应该是一个双射。换句话说，第二次运行中打印的所有矩阵都应该是第一次运行中对应矩阵的原像。此外，输出 $-1$ 的数量不应超过两个集合大小之差。

形式化地说，如果在第一次运行中你对某种类型的矩阵 $A$ 的回答是矩阵 $B$，而在第二次运行中你对相反类型的矩阵 $B$ 的回答是矩阵 $C$，则必须满足 $A = C$。此外，对于每个 $n$ 和每种矩阵类型，令 $U$ 为该类型所有 $n \times n$ 矩阵的集合，$V$ 为另一种类型 $n \times n$ 矩阵的集合。那么，对于来自 $U$ 的矩阵，你最多可以对 $\max(|U| - |V|, 0)$ 个不同的矩阵回答 $-1$。

样例

输入 1

3
lucky
2
11
11
good
2
11
01
lucky
2
01
10

输出 1

2
11
10
2
11
01
2
01
10

输入 2

3
good
2
11
10
lucky
2
11
01
good
2
01
10

输出 2

2
11
11
2
11
01
2
01
10