Một ông nông dân muốn cắt 1 thanh gỗ có độ dài L của mình thành N miếng, mỗi miếng có độ dài là một số nguyên dương a_i (a₁ + a₂ + … + a_N = L ). Tuy nhiên để cắt một miếng gỗ có độ dài là X thành 2 phần thì ông ta sẽ mất X tiền . Vì ông không giỏi tính toán nên bạn hãy tính giúp xem cần để dành ít nhất bao nhiêu tiền thì mới có thể cắt được tấm gỗ như mong muốn .

Dữ liệu: Có cấu trúc như sau:

- Dòng đầu tiên chứa một số nguyên dương T là số bộ test (T ≤ 100);

- T nhóm dòng tiếp theo mô tả các bộ test, mỗi nhóm dòng gồm 2 dòng:

+ Dòng đầu tiên chứa một số nguyên dương N (N ≤ 2.10⁴);

+ Dòng thứ hai chứa N số nguyên dương a₁, a₂, …, a_N ( 1 ≤ a_i ≤ 5.10⁴). Hai số liên tiếp trên cùng một dòng được cách nhau bởi một dấu cách.

Kết quả: Kết quả mỗi test ghi ra trên một dòng, ghi ra một số nguyên dương duy nhất là chi phí tối thiểu cần để cắt tấm gỗ.