Cho dãy số nguyên không âm ~a_1 a_2... a_n~. Người ta muốn chọn 2 chỉ số i, j sao cho 1 ≤ i ≤ j ≤ N và xoá khỏi dãy 2 số ~a_i~, ~a_j~ để tổng giá trị các số còn lại trong dãy là số chẵn.

Yêu cầu: Hãy đếm số lượng cách chọn 2 chỉ số i, j thoả mãn. Hai cách chọn khác nhau nếu tồn tại một chỉ số khác nhau.

Dữ liệu vào:

Từ tập tin văn bản XOASO.INP có cấu trúc như sau:

• Dòng đầu tiên lưu số nguyên T (1 ≤ T ≤ ~10^3~) - số test case của bài toán.
• Dòng đầu tiên của mỗi test chứa một số nguyên N.
• Dòng thứ hai chứa N số nguyên không âm ~a_1~ ~a_2~... ~a_n~ (~a_i~ ≤ ~10^9~) cách nhau 1 khoảng trắng.

Dữ liệu ra:

Ghi ra tập tin văn bản XOASO.OUT tương ứng với mỗi bộ test mỗi dòng in ra một số nguyên là số cách chọn 2 chỉ số thoả nếu không thì cách chọn nào thì in ra -1

Subtasks

Subtask #1 (30 điểm):

• T= 1, N ≤ 10

Subtask #2 (40 điểm):

• T = 10, N ≤ 106

Subtask #3 (30 điểm): ràng buộc gốc

Ví dụ:

XOASO.INP

1
5
1 2 3 4 5

XOASO.OUT

6

Giải thích

• Có 6 cách chọn 2 chỉ số i, j là:
• (i = 1, j = 2) tổng còn lại a3+ a4+ a5 = 3 + 4 + 5 = 12 là số chẵn.
• Tương tự: (i = 1, j = 4) và (i = 2, j = 3) và (i = 2, j = 5) và (i = 3, j = 4) và (i = 4, j = 5)