Little Q 正在玩一款 RPG 网络游戏。在这个游戏中，有 $n$ 个角色，编号为 $1, 2, \dots, n$。第 $i$ 个角色有三种类型的配额：

• $a_i$ - 他在 15 秒内能达到的最大伤害点数。
• $b_i$ - 他在 40 秒内能达到的最大伤害点数。
• $c_i$ - 他在 120 秒内能达到的最大伤害点数。

你是团队负责人，负责这 $n$ 个角色之间的新平衡，旨在为弱势角色带来希望。对于每个角色，你的队友制定了一个加强某些技能的计划，使得这三个配额可能会因此增加。注意，不允许削弱角色，因为这会让他们的拥有者感到不满。

为了实现完美的平衡，你需要接受一些计划并拒绝另一些计划，使得这 $n$ 个角色之间的差距最小化。注意，一个计划只能被完全接受或完全拒绝。在这里，差距定义为：

$$\max\{ \max_{1 \le i \le n} a_i - \min_{1 \le i \le n} a_i, \max_{1 \le i \le n} b_i - \min_{1 \le i \le n} b_i, \max_{1 \le i \le n} c_i - \min_{1 \le i \le n} c_i \}$$

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 100$)，表示测试用例的数量。对于每个测试用例： 第一行包含一个整数 $n$ ($1 \le n \le 100\,000$)，表示角色的数量。 接下来的 $n$ 行中，第 $i$ 行包含六个整数 $a_i, b_i, c_i, a'_i, b'_i$ 和 $c'_i$ ($1 \le a_i \le a'_i \le 10^9, 1 \le b_i \le b'_i \le 10^9, 1 \le c_i \le c'_i \le 10^9$)，描述了第 $i$ 个角色当前的配额以及计划中的配额。

保证所有 $n$ 的总和不超过 $500\,000$。

输出格式

对于每个测试用例，输出一行包含一个整数，表示最优差距。

样例

输入 1

1
2
1 1 1 2 3 5
2 4 3 7 5 8

输出 1

2