Trong đợt tập huấn mùa hè chuẩn bị cho kỳ thi ICPC năm sau, có một team của IUH tên là Lu senpai ureshii tham gia kỳ thi Code-end run để trải nghiệm. Sau khi vượt qua nhiều vòng, team đã được đi trải nghiệm thực tế tại cty Chợ Tốt và gặp nhiều senpai. Trong giờ nghỉ giải lao, các senpai trong cty có tổ chức một trò chơi nho nhỏ cho tất cả team tham gia. Tất cả người chơi sẽ được nhận một số nguyên có giá trị là: ~0, 1~ hoặc số nguyên tố không vượt quá ~23~. Yêu cầu của các senpai rất đơn giản: những người chơi hãy tìm cách ghép với nhau thành nhiều nhóm nhất sao cho tích các số của các thành viên trong nhóm đang giữ là bằng nhau. Các bạn hãy giúp cho các team ấy nhé, vì họ đang có tâm lý đi chơi chứ hơi lười nghĩ thuật toán.

Input:

Dòng đầu tiên gồm số nguyên dương ~n~, cho biết tổng số thành viên của các team tham gia, trong đó ~2 \le n \le 10^5.~

Dòng tiếp theo gồm ~n~ số tự nhiên, mỗi số có thể là ~0, 1~ hoặc là số nguyên tố không vượt quá ~23.~

Output:

Số nhóm nhiều nhất có thể chia ra.

Sample input 1:

4
0 1 2 3

Sample output 1:

1

Sample input 2:

4
2 2 3 3

Sample output 2:

2

Giải thích:

Trong VD1, ta thấy không có cách chia thành các nhóm nhỏ nào nên chỉ có 1 nhóm là tất cả các số ban đầu. Trong VD2, ta có thể chia thành 2 nhóm, mỗi nhóm gồm ~(2,3).~