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

Input

7
2 3 5 7 12 8 6

Output

0 4 1 1