Cho dãy số nguyên A[1], A[2], …, A[N]. Hãy đếm số lượng các dãy con liên tiếp có tổng chẵn trong dãy đã cho.

Đầu vào: Dòng đầu tiên chứa một số nguyên T biểu thị số bộ dữ liệu kiểm tra. Mỗi bộ dữ liệu gồm:

+ Dòng đầu chứa một số nguyên N cho biết số phần tử của dãy đã cho.

+ Dòng tiếp theo chứa N số nguyên được phân cách bằng dấu cách biểu thị các phần tử của dãy đã cho.

Đầu ra: Ứng với mỗi bộ dữ liệu vào, in ra một dòng chứa câu trả lời tương ứng.

Ràng buộc:

+ 1 ≤ T ≤ 200; 1 ≤ N ≤ 1000;

+ 1 ≤ A[i]  ≤ 100, i = 1…N;

Ví dụ