Yêu cầu:

Cho 1 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 1 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 𝑛 ~(1 \le n \le 10^6)~
• Dòng 2: Ghi 𝑛 số nguyên ~A_1, A_2,...,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:

Input:

7
2 3 5 7 12 8 6

Output:

0 4 1 1