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\) (\(0 < n \leq 10^5\)).
• Dòng tiếp theo ghi \(n\) số nguyên dương \(a_i\) (\(1 \leq i \leq n; a_i \leq 10^9\)).

Output

• Ghi một số nguyên duy nhất cho biết số lượng số may mắn có trong dãy.

Example

4
4 8 12 15

2

Scoring

• Subtask \(1\) (\(80\%\) số điểm): \(n \leq 10^3; a_i \leq 10^6\).
• Subtask \(2\) (\(20\%\) số điểm): không có ràng buộc gì thêm.