H. Command and Conquer: Red Alert 2
time limit per test
10 seconds
memory limit per test
512 mebibytes
input
standard input
output
standard output

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?

Input

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$$$.

Output

For each test case, output a line with a single integer representing the answer.

Example
Input
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
Output
0
1
2