Command and Conquer: Red Alert 2

Nocriz is a nostalgic boy who loves watching HBK08 and Lantian28 play Command and Conquer: Red Alert 2. However, he does not know how to play the game himself.

In the game, you own a sniper initially located at $(-10^{100}, -10^{100}, -10^{100})$ in a 3D world. There are $n$ enemy soldiers, where the $i$-th soldier is located at $(x_i, y_i, z_i)$. We say the range of the sniper is $k$ if the sniper can kill all enemies such that $\max(|x_s - x_e|, |y_s - y_e|, |z_s - z_e|) \le k$, where $(x_s, y_s, z_s)$ is the location of the sniper and $(x_e, y_e, z_e)$ is the location of the enemy.

In one step, the sniper can move from $(x, y, z)$ to $(x + 1, y, z)$, $(x, y + 1, z)$, or $(x, y, z + 1)$. The enemies do not move. The sniper may make an unlimited number of steps and may kill all enemies in range whenever all of its coordinates are integers. What is the minimum range $k$ such that the sniper can eventually kill all enemies?

The first line contains an integer $T$ ($1 \le T \le 5 \cdot 10^4$), the number of test cases. Then $T$ test cases follow.

The first line of each test case contains a single integer $n$ ($1 \le n \le 5 \cdot 10^5$), the number of enemies.

Then $n$ lines follow, each containing three integers $x_i$, $y_i$, $z_i$ ($-10^9 \le x_i, y_i, z_i \le 10^9$) denoting the location of the $i$-th enemy.

It is guaranteed that $\sum n \le 2 \cdot 10^6$.

For each test case, output a line with a single integer representing the minimum range $k$.