Cho một dãy gồm \(n\) số nguyên dương \(a_1,a_2,...,a_n. \)

Yêu cầu: Hãy lập trình đếm số các số nguyên dương trong dãy đã cho có tổng các ước là một số chẵn.

Dữ liệu vào:

• Dòng đầu chứa số nguyên dương \(n (1≤n≤1000)\) là số phần tử của dãy;

• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1,a_2,...,a_n (1≤a_i≤1000,i=1,2,...,n)\) các số cách nhau một dấu cách.

Kết quả:

• Ghi số các số nguyên dương của dãy đã cho có tổng các ước là số chẵn.

Sample Input

4
1 4 8 5

Sample Output

1

Sample Input

3
2 10 5

Sample Output

2