Hôm nay Lan tìm hiểu về lý thuyết số học. Bạn ấy cảm thấy vô cùng thích thú khi tìm hiểu về chủ đề phân tích một số ra thừa số nguyên tố. Mỗi số nguyên dương \(x\) bất kỳ đều có thể được biểu diễn dưới dạng tích của các số nguyên tố, và biểu diễn này là duy nhất.

Để khám phá kiến thức mới này, Lan tiến hành vẽ ``cây phân tích thừa số nguyên tố''. Đây là một cây được cố định gốc, và mỗi nút trên cây có chứa một số nguyên dương. Cây cần thỏa mãn các điều kiện sau:

• Giá trị của nút gốc là một số nguyên dương lớn hơn \(1\).
• Nếu một nút là lá, giá trị của nó phải là một số nguyên tố.
• Nếu một nút khác lá, giá trị của nó phải bằng tích giá trị của các con của nó.

Lan có một dãy số yêu thích \(a_1, a_2, \ldots, a_n\). Lan muốn tạo ra một cây phân tích chứa tất cả các giá trị trong dãy số này. Nói cách khác, trên cây cần có \(n\) nút đôi một phân biệt sao cho giá trị của chúng lần lượt là \(a_1, a_2, \ldots, a_n\). Chỉ có điều, cây của Lan thường rất lớn. Bạn hãy giúp Lan xây dựng một cây phân tích hợp lệ có số đỉnh nhỏ nhất nhé.

Input

• Dòng thứ nhất chứa số nguyên \(n\) \((1 \leq n \leq 15)\).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) \((2 \le a_i \le 10^{15})\).

Output

Gồm một dòng duy nhất chứa số đỉnh nhỏ nhất của một cây phân tích chứa toàn bộ giá trị trong \(a\).

Scoring

• Subtask \(1\) (\(8\) điểm): \(n = 1\)
• Subtask \(2\) (\(18\) điểm): Tất cả các số \(a_1, a_2, \ldots, a_n\) đều là số nguyên tố.
• Subtask \(3\) (\(14\) điểm): Tồn tại \(n\) số nguyên tố \(p_1, p_2, \ldots, p_n\) và \(n\) số nguyên dương \(e_1, e_2, \ldots, e_n\) sao cho \(a_i = p_i^{e_i}\) với mọi \(i\) từ \(1\) đến \(n\).
• Subtask \(4\) (\(20\) điểm): \(n \leq 5\)
• Subtask \(5\) (\(22\) điểm): \(n \leq 10\)
• Subtask \(6\) (\(18\) điểm): Không có ràng buộc gì thêm.

Example

3
21 6 24

10