23155번 - Command and Conquer: Red Alert 2 다국어

Being a nostalgic boy, Nocriz loves watching HBK08 and Lantian28 playing the game Command and Conquer: Red Alert 2. However, he doesn't 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 to be $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 don't move. The sniper is allowed to make an unlimited number of steps, and is allowed to kill all enemies in range whenever all his 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 contains 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 answer.