Ở một thị trấn nhỏ có một xưởng chuyên về đồ gỗ. Vì thị trấn nhỏ nên chỉ có ba người thợ chạm khắc làm việc ở đó. Sắp tới, một lễ hội đồ chơi bằng gỗ sẽ được tổ chức tại thị trấn. Các nhân viên xưởng muốn chuẩn bị cho lễ hội này. Họ biết rằng n người sẽ đến xưởng với yêu cầu làm một món đồ chơi bằng gỗ. Mọi người đều khác nhau và có thể muốn những món đồ chơi khác nhau. Để đơn giản, chúng ta hãy biểu thị mẫu đồ chơi mà người thứ i muốn là ai (1 ≤ ai ≤ 10^9).

Mỗi người thợ chạm khắc có thể chọn một mẫu là số nguyên x (1 ≤ x ≤​10^9) và trước đó những người thợ chạm khắc khác nhau có thể chọn những mẫu x khác nhau. Trong quá trình chuẩn bị cho lễ hội, những người thợ chạm khắc sẽ hoàn thiện kỹ thuật làm đồ chơi theo mẫu đã chọn, cho phép họ cắt nó ra khỏi gỗ ngay lập tức. Để làm đồ chơi theo mẫu y cho một người thợ chạm khắc đã chọn mẫu x, nó sẽ mất |x-y| thời gian, vì đồ chơi càng giống với đồ chơi mà người thợ có thể làm ra ngay lập tức thì người thợ sẽ hoàn thành công việc càng nhanh.

Vào ngày lễ hội, khi người tiếp theo đến xưởng với yêu cầu làm đồ chơi bằng gỗ, những người thợ chạm khắc có thể chọn người sẽ đảm nhận công việc. Đồng thời, những người thợ chạm khắc là những người rất lành nghề và có thể làm việc theo đơn đặt hàng của nhiều người cùng một lúc.

Vì mọi người không thích chờ đợi nên những người thợ chạm khắc muốn chọn mẫu để chuẩn bị sao cho thời gian chờ đợi tối đa của tất cả mọi người là ngắn nhất có thể.

Hãy đưa ra thời gian chờ tối đa tốt nhất mà người thợ chạm khắc có thể đạt được.

Định dạng đầu vào và ràng buộc:

Dòng đầu tiên của đầu vào chứa một số nguyên t (1 ≤ t ≤​10^4) là số lượng trường hợp thử nghiệm.

Sau đó là mô tả của các trường hợp thử nghiệm.

Dòng đầu tiên của một trường hợp thử nghiệm chứa một số nguyên duy nhất n (1 ≤ n ≤ 2.10^5) là số lượng người sẽ tham dự lễ hội.

Dòng thứ hai của một trường hợp thử nghiệm chứa𝑛số nguyên a1, a2, ... , an (1 ≤ ai ≤10^9) là các mẫu đồ chơi.

Tổng của tất cả n giá trị trên tất cả các trường hợp thử nghiệm không vượt quá 2.10^5

Định dạng đầu ra: Đầu ra t các con số, mỗi con số là câu trả lời cho trường hợp thử nghiệm tương ứng là thời gian chờ tối đa tốt nhất mà người thợ chạm khắc có thể đạt được.

Input:

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

Output:

0 
2 
13 
0 
1

Giải thích:

Trong ví dụ đầu tiên, người thợ chạm khắc có thể chọn mẫu 1,7,9 để chuẩn bị.

Trong ví dụ thứ hai, người thợ chạm khắc có thể chọn mẫu 3, 30,60 để chuẩn bị.

Trong ví dụ thứ ba, người thợ chạm khắc có thể chọn mẫu 14, 50, 85 để chuẩn bị.