Cây ước số

Một cây ước số là một cây có gốc thoả mãn đồng thời ba điều kiện sau:

• Mỗi đỉnh của cây chứa một số nguyên dương.
• Số ghi ở mỗi đỉnh lá là một số nguyên tố.
• Với mỗi đỉnh trong (đỉnh có ít nhất một con), số ghi ở đỉnh đó bằng tích các số ghi ở tất cả các con của nó.

Cho $n$ số nguyên phân biệt $a_1,a_2,\dots ,a_n$. Hãy xây dựng một cây ước số chứa tất cả các số này, nghĩa là với mỗi $a_i$ phải có ít nhất một đỉnh của cây ghi số $a_i$. Ngoài các số đã cho, cây được phép chứa thêm các đỉnh với giá trị tuỳ ý, miễn là ba điều kiện trên vẫn đúng.

Nhiệm vụ của bạn là tìm số đỉnh nhỏ nhất có thể của một cây ước số như vậy.

Dữ liệu vào

• Dòng đầu chứa một số nguyên $n$: số lượng số đã cho.
• Dòng thứ hai chứa $n$ số nguyên phân biệt $a_1,a_2,\dots ,a_n$.

Dữ liệu ra

Một số nguyên duy nhất: số đỉnh nhỏ nhất của cây ước số chứa tất cả $n$ số đã cho.

Ràng buộc

• $1\le n\le 8$
• $2\le a_i\le {10}^{12}$
• Các $a_i$ đôi một phân biệt.

Ví dụ