Nguyên tố cùng nhau

Sau khi tham gia tổ chức lễ hội làng quê, Hiếu lại quay trở lại phòng nghiên cứu TAS và đã tìm thấy cho mình một lĩnh vực nghiên cứu mới, đó là kĩ thuật mật mã và an toàn thông tin.

Hiếu mong muốn sẽ xây dựng được một phương thức mã hoá thông tin mới có độ an toàn gần như tuyệt đối. Phương thức mã hoá này được phát triển dựa trên ý tưởng về tập hợp các số nguyên tố cùng nhau.

Bước đầu tiên của nghiên cứu là: "Từ một tập hợp các số nguyên dương $S$, Hiếu muốn chọn ra một tập con $S^{\prime }$ có số phần tử nhiều nhất sao cho hai số bất kì trong tập con $S^{\prime }$ luôn nguyên tố cùng nhau".

Hai số nguyên dương được gọi là nguyên tố cùng nhau nếu ước chung lớn nhất của chúng bằng $1$. Tập con chỉ gồm một phần tử luôn thỏa mãn điều kiện trên.

Bạn hãy lập trình giúp Hiếu giải quyết vấn đề đơn giản này để Hiếu tập trung làm những phần việc quan trọng hơn.

Dữ liệu vào

• Dòng đầu tiên ghi một số nguyên dương $n$ là số lượng các số thuộc tập hợp $S$;
• Dòng thứ $i$ trong $n$ dòng tiếp theo ghi một số nguyên dương là số thứ $i$ của $S$. Các số thuộc $S$ đôi một khác nhau.

Dữ liệu ra

In ra một số nguyên là kích thước lớn nhất của tập con $S^{\prime }$ của $S$ mà hai số bất kì thuộc $S^{\prime }$ nguyên tố cùng nhau.

Ràng buộc

• Các số thuộc $S$ là các số nguyên dương đôi một khác nhau, không vượt quá $5000$ (do đó $1\le n\le 5000$).

Subtasks

• Có $\frac{1}{7}$ số test ứng với $\frac{1}{7}$ số điểm thỏa mãn: các số thuộc tập không vượt quá $20$;
• Có $\frac{3}{7}$ số test khác ứng với $\frac{3}{7}$ số điểm thỏa mãn: các số thuộc tập không vượt quá $100$;
• Có $\frac{3}{7}$ số test còn lại ứng với $\frac{3}{7}$ số điểm thỏa mãn: các số thuộc tập không vượt quá $5000$.

Ví dụ