“太安静了，”David Jr 自言自语道。他的太空舰队几分钟前进入了战场，但没有发现任何敌人的踪迹。飞船上的每个人都承受着巨大的压力，等待着敌人的攻击。

突然，警报响了。“等等，不是敌人。”David 意识到，“是仪器故障。”仪器故障的原因很快被查明：根据飞船的三维坐标计算出的飞船间距离，与通过通信延迟计算出的距离不符。“每艘船都发出了同样的警告，这表明这不仅仅是一个简单的仪器故障。好吧，只能用‘那个东西’来解释了。”David 相信敌人发明了“K维箔”（K-Dimensional Foil），这是一种终极武器，而他们正受到该武器的攻击。

“K维箔”是一种维度武器。它可以将三维空间中的一个区域提升到K维（$K \ge 3$）空间，这可能会对该区域内的物体造成巨大破坏。当飞船处于K维空间时，其坐标是一个K维坐标。但其计算机只知道原始的三维坐标，无法获取其他更高维度的坐标。因此，通过坐标计算出的飞船间距离是不正确的。但实际距离总是可以通过通信延迟计算出来。

David 是一个谨慎的人。他准备了一些防御“K维箔”的方法。然而，他必须知道他的舰队所处的空间维度数。这项光荣的任务交给了你，舰队的首席技术官。

现在，轮到你创造历史了……

输入格式

输入的第一行是一个整数 $T$ ($T \le 100$)，表示测试用例的数量。

对于每个测试用例，第一行包含一个整数 $n$ ($1 \le n \le 50$)，表示 David 舰队中的飞船数量。

接下来 $n$ 行，每行包含三个整数 $x, y, z$ ($-300 \le x, y, z \le 300$)，表示一艘飞船的三维坐标。

接下来 $n-1$ 行。第 $i$ 行包含 $n-i$ 个正整数。第 $j$ 个整数表示第 $i$ 艘飞船与第 $(i+j)$ 艘飞船之间的实际距离的平方（为了避免精度问题），该距离由通信延迟计算得出。

注意：本题中的距离为欧几里得距离。例如，在4维空间中，点 $(x_1, y_1, z_1, k_1)$ 与点 $(x_2, y_2, z_2, k_2)$ 之间的距离为 $\sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2 + (z_1 - z_2)^2 + (k_1 - k_2)^2}$。

输出格式

对于每个测试用例，输出一个整数 $K$，表示新空间可能的最小维度数。如果输入无法适配任何维度空间，则应输出“Goodbye World!”，不含引号。

样例

样例输入 1

3
3
0 0 1
0 0 2
0 0 3
10 20
26
3
1 0 0
2 0 0
3 0 0
3 7
20
3
0 0 0
1 1 1
2 2 2
3 12
3

样例输出 1

5
Goodbye World!
3

说明

样例 #1：在一种可能的情况下，这是一个5维空间，这三艘飞船的坐标分别是 $(0,0,1,0,0), (0,0,2,0,3), (0,0,3,4,0)$。

样例 #2：飞船1与飞船2、飞船1与飞船3之间的距离都很小，但飞船2与飞船3之间的距离太大。这意味着世界已经破碎，所以我们应该输出“Goodbye World!”。

样例 #3：看起来什么也没发生。