Cho một dãy số nguyên gồm \(n\) số cho trước. Hãy đếm tất cả các số chính phương, nguyên tố, hoàn hảo, phong phú trong dãy.

Giải thích

• Ước thực sự của một số là tập hợp tất cả các ước dương nhỏ hơn nó.
• Số chính phương là số có căn bậc \(2\) của nó là một số nguyên.
• Số nguyên tố là số chỉ có \(2\) ước là \(1\) và chính nó.
• Số hoàn hảo là số có tổng các ước thực sự của nó bằng chính nó. Ví dụ, số \(6\) có tổng các ước số (không kể \(6\)) là \(1 + 2 + 3 = 6\). Do đó \(6\) là một số hoàn hảo.
• Số phong phú là số có tổng các ước thực sự của số đó lớn hơn số đó. Ví dụ, số \(12\) có tổng các ước số (không kể \(12\)) là \(1 + 2 + 3 + 4 + 6 = 16 > 12\). Do đó \(12\) là một số phong phú.

Input

• Dòng 1: Ghi số nguyên \(n\) (\(1 \le n \le 10^6\)).
• Dòng 2: Ghi \(n\) số nguyên \(A_1, A_2, \dots, A_n\) (\(1 \le A_i \le 10^6\)).

Output

• Dòng 1: Ghi \(4\) số nguyên dương lần lượt là số lượng các số chính phương, nguyên tố, hoàn hảo, phong phú tìm được trong dãy.

Example

7
2 3 5 7 12 8 6

0 4 1 1