Số đặc biệt
Cho dãy số gồm n phần tử A = [a1, a2,…, an] (1 ≤ ai ≤ n) được cho trước. Phần tử ai của nó được gọi là đặc biệt nếu tồn tại một cặp chỉ số l và r (1 ≤ l < r ≤ n) sao cho ai = al + al + 1 +… + ar. Nói cách khác, một phần tử được gọi là đặc biệt nếu nó có thể được biểu diễn dưới dạng tổng của hai hoặc nhiều phần tử liên tiếp của một mảng (bất kể chúng có đặc biệt hay không).
Yêu cầu: In ra số phần tử đặc biệt của mảng đã cho A.
Ví dụ, nếu n = 9 và A = [3,1,4,1,5,9,2,6,5], thì câu trả lời là 5:
a3 = 4 là một phần tử đặc biệt, vì a3 = 4 = a1 + a2 = 3 + 1;
a5 = 5 là một phần tử đặc biệt, vì a5 = 5 = a2 + a3 = 1 + 4;
a6 = 9 là một phần tử đặc biệt, vì a6 = 9 = a1 + a2 + a3 + a4 = 3 + 1 + 4 + 1;
a8 = 6 là một phần tử đặc biệt, vì a8 = 6 = a2 + a3 + a4 = 1 + 4 + 1;
a9 = 5 là một phần tử đặc biệt, vì a9 = 5 = a2 + a3 = 1 + 4.
Lưu ý rằng một số phần tử của dãy sỗ có thể bằng nhau, nếu một số phần tử bằng nhau và đặc biệt, thì tất cả chúng sẽ được tính là đặc biệt.
Input
Dòng đầu tiên chứa một số nguyên t (1 ≤ t ≤ 1000) - số lượng test case trong đầu vào. Sau đó, t các test case theo sau.
Mỗi test case được đưa ra trong hai dòng:
+ Dòng đầu tiên chứa số nguyên n (1 ≤ n ≤ 8000) - độ dài của dãy số.
+ Dòng thứ hai chứa các số nguyên a1, a2,…, an (1 ≤ ai ≤ n; i = 1, 2, …, n).
Đảm bảo rằng tổng các giá trị của n cho tất cả các test case trong đầu vào không vượt quá 8000.
Output
In ra t số - số phần tử đặc biệt của mỗi dãy số đã cho.
Ví dụ: