Số may mắn là những con số có số lượng ước nguyên dương là chẵn và tổng các chữ số của nó cũng là một số chẵn. Ví dụ số 15 là số may mắn vì 15 có 4 ước là 1, 3, 5, 15 và tổng chữ số của 15 là 6. Số 4 không phải số may mắn vì 4 có 3 ước là 1, 2, 4 (số lượng ước không phải số chẵn).

Cho một dãy gồm n số nguyên dương. Cho biết số lượng số may mắn trong dãy đã cho.

Input

• Dòng đầu tiên ghi số nguyên n (n ≤ 10^5).
• Dòng tiếp theo ghi n số nguyên dương ai (1 ≤ i ≤ n; ai ≤ 10^9).

(các số trên ~1~ dòng được ghi cách nhau ~1~ dấu cách)

Output

• Ghi kết quả bài toán

Sample input

5
9 24 8 16 15

Sample output

3

Subtask

• ~50\%~ số test có ~n \le 1000, ai \le10^6~
• ~50\%~ số test còn lại không có điều kiện gì thêm