Trong một trò chơi máy tính, nhiệm vụ của người chơi là phải tiêu diệt hết quái vật để được thăng cấp. Quái vật thứ \(i\) có lượng máu là \(a_i\) và lượng máu của tất cả quái vật đều là số nguyên. Một con quái vật được gọi là còn sống nếu máu của nó còn lớn hơn \(0\).

Để tiêu diệt đám quái vật, người chơi có thể thực hiện 2 loại thao tác sau:

• 1. Chọi trứng vào 1 quái vật bất kì để gây 1 sát thương lên quái vật đó.
• 1. Phóng tên lửa vào những quái vật còn sống để gây 1 sát thương lên những quái vật đó. Nếu có ít nhất 1 quái vật chết sau khi sử dụng thao tác loại 2, thì có thể lặp lại thao tác này đến khi không còn quái vật nào chết khi sử dụng thao tác nữa.

Gây 1 sát thương lên quái vật là giảm lượng máu của quái vật đó xuống 1 đơn vị.

Trong trò chơi, thao tác loại 1 có thể sử dụng nhiều lần, trong khi thao tác loại 2 chỉ có thể sử dụng một lần xuyên suốt quá trình chơi.

Số lần lượng thao tác loại 1 ít nhất mà người chơi có thể dùng để giết hết tất cả quái vật là bao nhiêu?

Input:

• Dòng đầu là một số nguyên \(t\) \((1 \le t \le 10^3)\) là số lượng test case.
• Dòng đầu của mỗi test case chứ 1 số nguyên \(n\) \((1 \le n \le 10^3)\) là số lượng quái vật.
• Dòng thứ hai chứa \(n\) số nguyên \(a_1,a_2,...a_n(1 \le a_i \le n)-\) là lượng máu của những con quái vật.

Output:

• Mỗi test case in ra một số nguyên là số lần thao tác loại 1 ít nhất để tiêu diệt \(n\) quái vật.

Examples:

Input:

2
3
3 1 2
6
4 1 5 4 1 1

Output:

0
4

Giải thích:

Ở test case đầu tiên, máu của quái vật lần lượt là [3,1,2]. Đủ để chúng ta sử dụng thao tác loại 2:

• Máu của tất cả quái vật giảm xuống \([2,0,1]\). Vì quái vật thứ \(2\) đã bị tiêu diệt, chúng ta có thể lặp lại thao tác này.
• Máu của tất cả quái vật giảm xuống \([1,0,0]\). Vì quái vật thứ \(3\) đã bị tiêu diệt, chúng ta có thể lặp lại thao tác này.
• Máu của tất cả quái vậy giảm còn \([0,0,0]\). Vì quái vật thứ \(1\) đã bị tiêu diệt, chúng ta có thể lặp lại thao tác này.
• Vậy nên không cần sử dụng thao tác một mà người chơi vẫn có thể tiêu diệt được quái vật.

Ở test case thứ hai, máu của quái vật lần lượt là \([4,1,5,4,1,1].\) Chúng ta có thể thực hiện các thao tác như sau:

• Thực hiện thao tác loại 1, gây \(1\) sát thương lên quái vật ở vị trí \(1\). Máu của quái vật giảm còn \([3,1,5,4,1,1].\)
• Thực hiện thao tác loại 1, gây \(1\) sát thương lên quái vật ở vị trí \(4\). Máu của quái vật giảm còn \([3,1,5,3,1,1].\)
• Thực hiện thao tác loại 1, gây \(1\) sát thương lên quái vật ở vị trí \(4\) một lần nữa. Máu của quái vật giảm còn \([3,1,5,2,1,1].\)
• Thực hiện thao tác loại 2:
• Máu của quái vật giảm còn \([2,0,4,1,0,0].\) Vì quái vật thứ \(2,5,6\) đã bị tiêu diệt, chúng ta có thể lặp lại thao tác này.
• Máu của quái vật giảm còn \([1,0,3,0,0,0].\) Vì quái vật thứ \(4\) đã bị tiêu diệt, chúng ta có thể lặp lại thao tác này.
• Máu của quái vật giảm còn \([0,0,2,0,0,0].\) Vì quái vật thứ \(1\) đã bị tiêu diệt, chúng ta có thể lặp lại thao tác này.
• Máu của quái vật giảm còn \([0,0,1,0,0,0].\) Vì không có quái vật nào bị tiêu diệt, thao tác không được lặp lại.
• Thực hiện thao tác loại 1, tiêu diệt quái vật thứ \(3\). Vậy chúng ta cần ít nhất \(4\) lần thao tác loại 1 để tiêu diệt hết tất cả quái vật.