Marisa rất thích sưu tầm sao. Một hôm, Marisa phát hiện ra rằng có thể xếp các ngôi sao thành một tam giác vuông cân.Cho \(n\) túi sao, mỗi túi chứa một số lượng sao \(a_i\) khác nhau. Hãy giúp Marisa xác định có bao nhiêu túi hợp lệ có thể xếp thể xếp thành tam giác vuông cân. Quy ước \(1\) ngôi sao cũng được xem là một tam giác vuông cân hợp lệ.

Input

- Dòng đầu chứa số nguyên \(n\) — số lượng túi sao.
- Dòng thứ hai chứa \(a_1\) , \(a_2\) , ... , \(a_n\) số nguyên

Ràng buộc:
- \(1 \le n \le 10^5\)
- \(1 \le a_i \le 10^{18}\)

Output

- Trên 1 dòng , in ra số túi sao hợp lệ

Example

5
2 3 5 6 12 

2

Các túi hợp lệ là 3 và 6