题目描述

Aki 的工坊里有 3 位工匠，他们要为展会提前各自练熟一种“样式”。

共有 n 位顾客，第 i 位顾客想要的玩具样式编号为 a_i。

每位工匠可以预先选择一个整数样式编号 x。如果某位工匠预练的是 x，那么他制作样式 y 的玩具所需时间为 |x-y|.

展会当天，3 位工匠可以并行工作。对于每位顾客，可以自由决定由哪位工匠来制作。

请你最小化“所有顾客中，制作时间的最大值”。

也就是说，你需要求出一个最小的整数 T，使得可以为 3 位工匠分别选择预练样式，并让每位顾客都能分配给某位工匠，且其制作时间不超过 T。

输入格式

第一行一个整数 t 表示测试组数，满足 1≤ t≤ 10⁴。

每组测试数据包含两行。

第一行一个整数 n，满足 1≤ n≤ 2× 10⁵。

第二行 n 个整数 a₁,a₂,…,a_n，满足 1≤ a_i≤ 10⁹。

所有测试组的 n 之和不超过 2× 10⁵。

输出格式

对于每组测试数据，输出一个整数，表示最优方案下的最小最大制作时间。

5
6
1 7 7 9 9 9
6
5 4 2 1 30 60
9
14 19 37 59 1 4 4 98 73
1
2
6
3 10 1 17 15 11

0
2
13
0
1