Trừ tối thiểu

Bối cảnh

An có một mảng \(a\) gồm \(n\) số nguyên. Nếu mảng \(a\) có độ dài lớn hơn 1 thì An có thể áp dụng thao tác gọi là trừ tối thiểu cho nó như sau:

Yêu cầu

• Đầu tiên, An tìm số \(m\) nhỏ nhất trong mảng. Nếu có nhiều số nhỏ nhất thì An có thể chọn bất kỳ số nào trong chúng;

• Sau đó, phần tử nhỏ nhất đã chọn sẽ bị xóa khỏi mảng. Tiếp theo, mỗi phần tử còn lại của mảng được trừ đi \(m\).

Như vậy sau mỗi thao tác, độ dài của mảng giảm đi \(1\).

Ví dụ nếu \(a = [1, 6, -4, -2, -4]\) thì phần tử nhỏ nhất trong đó là \(a_3 = -4\) và sau thao tác này, mảng sẽ trở thành \(a = [1-(-4), 6-(-4), -2-(-4), -4-(-4)] = [5, 10, 2, 0]\)

Vì An thích những số lớn, nên anh ấy muốn các số trong mảng \(a\) càng lớn càng tốt. Cụ thể, anh ta muốn làm cho số nhỏ nhất trong mảng \(a\) là lớn nhất. Để thực hiện điều này, An có thể áp dụng thao tác trừ tối thiểu cho mảng nhiều lần tùy thích (có thể không thao tác lần nào). Lưu ý rằng thao tác này không thể áp dụng cho mảng có độ dài \(1\).

Hãy giúp An tìm giá trị lớn nhất của phần tử nhỏ nhất của mảng sau khi áp dụng một số (có thể bằng \(0\)) thao tác trừ tối thiểu cho mảng.

Input

Dòng đầu tiên chứa một số nguyên \(t\ (1\leq t\leq 10^3)\) là số lượng test.

Dòng thứ nhất của mỗi test chứa số nguyên \(n\ (1\leq 10^3)\) là độ dài ban đầu của mảng \(a\);

Dòng thứ hai của mỗi test chứa \(n\) số nguyên \(a_1, a_2,...,a_n\ (-10^9 \le a_i \le 10^9)\) là các phần tử của mảng \(a\)

Dữ liệu vào đảm bảo rằng tổng độ dài các mảng trên tất cả các test không vượt quá \(10^3\).

Output

In ra một số nguyên duy nhất là kết quả của bài toán.

Ràng buộc

Đề gốc không nêu ràng buộc riêng.

Ví dụ 1

Input

4
1
10
2
0 0
3
-1 2 0
4
2 10 1 7

Output

10
0
2
5

Giải thích ví dụ

• Ví dụ 1:

  • Dữ liệu: a = [1, 6, -4, -2, -4]
  • Giải thích: Sau khi thực hiện thao tác trừ tối thiểu, số nhỏ nhất trong mảng có thể đạt giá trị tối đa là 5.

• Ví dụ 2:

  • Dữ liệu: a = [-1, 2, 0]
  • Giải thích: Sau khi thực hiện thao tác trừ tối thiểu, số nhỏ nhất trong mảng có thể đạt giá trị tối đa là 2.

Thông tin học tập

• Buổi: B16
• Concepts: sorting, sequence transformations, difference reasoning
• Giới hạn kiến thức: B01-B16
• Time limit: 1 second
• Memory limit: 20 MB
• Point: 15