Cho số nguyên dương ~n~ và dãy số nguyên dương gồm ~n~ phần tử ~a_1,a_2,…,a_n~.

Yêu cầu: Ghi ra 5 số nguyên theo thứ tự là số lượng các loại số: chính phương, nguyên tố, hoàn hảo, phong phú, T-prime có trong dãy đã cho.

Số hoàn hảo là số có tổng các ước(không kể ước chính nó) bằng chính nó, số T-prime là số có đúng 3 ước, các loại số còn lại học sinh tự hiểu.

Input

• Dòng 1 chứa số nguyên dương ~n~ (~1≤n≤10^5~).
• Dòng 2 chứa ~n~ số nguyên là giá trị của các phần tử từ ~a_1,a_2,…,a_n~ (~1≤a_i≤10^6~)

Output

• Gồm 1 dòng duy nhất gồm 5 số nguyên dương theo thứ tự là số lượng các loại số: chính phương, nguyên tố, hoàn hảo, phong phú, T-prime mỗi số ngăn cách nhau bởi dấu cách.

Scoring

• Có 70% số test ứng với 70% số điểm thỏa mãn: ~n≤10^3~ và ~a_i≤10^3~;
• Có 15% số test ứng với 15% số điểm thỏa mãn: ~n≤10^3~ và ~a_i≤10^6~;
• Có 15% số test còn lại ứng với 15% số điểm không có ràng buộc gì thêm.

Examples

Input

4
3 8 9 23

Output

1 2 0 0 1