作为一个怀旧的男孩，Nocriz 很喜欢看 HBK08 和 Lantian28 玩《命令与征服：红色警戒 2》。然而，他自己并不会玩这个游戏。

在游戏中，你拥有一个狙击手，初始位于 3D 世界中的 $(-10^{100}, -10^{100}, -10^{100})$。场上有 $n$ 个敌方士兵，其中第 $i$ 个士兵位于 $(x_i, y_i, z_i)$。我们称狙击手的射程为 $k$，如果狙击手能够击杀所有满足 $\max(|x_s - x_e|, |y_s - y_e|, |z_s - z_e|) \le k$ 的敌人，其中 $(x_s, y_s, z_s)$ 是狙击手的位置，$(x_e, y_e, z_e)$ 是敌人的位置。

在每一步中，狙击手可以从 $(x, y, z)$ 移动到 $(x+1, y, z)$、$(x, y+1, z)$ 或 $(x, y, z+1)$。敌人不会移动。狙击手可以进行无限次移动，并且只要他的坐标均为整数，就可以击杀范围内的所有敌人。求狙击手最终能够击杀所有敌人所需的最小射程 $k$。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 5 \cdot 10^4$)，表示测试用例的数量。接下来是 $T$ 个测试用例。

每个测试用例的第一行包含一个整数 $n$ ($1 \le n \le 5 \cdot 10^5$)，表示敌人的数量。

接下来 $n$ 行，每行包含三个整数 $x_i, y_i, z_i$ ($-10^9 \le x_i, y_i, z_i \le 10^9$)，表示第 $i$ 个敌人的位置。

保证 $\sum n \le 2 \cdot 10^6$。

输出格式

对于每个测试用例，输出一行，包含一个整数，表示答案。

样例

样例输入 1

3
2
0 0 0
1 1 1
2
0 1 0
1 0 1
5
1 1 4
5 1 4
1 9 1
9 8 1
0 0 0

样例输出 1

0
1
2