Mô tả

Chương trình thực hiện biến đổi một mảng số nguyên dương (A[]) thành mảng đối xứng với số lần thực hiện phép Merge(A[i], A[i+1]) ít nhất.

Định nghĩa phép Merge:

• Merge(A[i], A[i+1]) = A[i] + A[i+1], đồng thời loại bỏ A[i+1] khỏi mảng.
• Ví dụ: Với A[] = {3, 2, 3, 3, 5}, sau 1 lần Merge, mảng trở thành {5, 3, 3, 5}.

Đầu vào

1. Dòng đầu tiên là số lượng bộ test (T) (1 ≤ (T) ≤ 100).
2. Tiếp theo là (T) bộ test. Mỗi bộ test bao gồm:
   • Dòng 1: Số phần tử (n) của mảng (A[]) (1 ≤ (n) ≤ 10³).
   • Dòng 2: (n) số nguyên (A[i]) (1 ≤ (A[i]) ≤ 10³), cách nhau bởi dấu cách.

Đầu ra

• Với mỗi bộ test, in ra số lần Merge ít nhất cần thực hiện để mảng trở thành đối xứng.

Ví dụ

Đầu vào:

2
5
3 2 3 3 5
4
5 3 3 4

Đầu ra:

1
3