| Codeforces Round 196 (Div. 2) |
|---|
| Закончено |
Дерево делителей — это корневое дерево, для которого выполняются следующие условия:
- В каждой из вершин дерева записано целое положительное число.
- В листьях дерева записаны простые числа.
- Для любой внутренней вершины произведение чисел, записанных в ее сыновьях, равно числу, записанному в этой вершине.
У Манао есть n различных чисел a1, a2, ..., an. Он пытается построить такое дерево делителей, в вершинах которого каждое из ai будет встречаться хотя бы по одному разу. Манао любит компактность, но деревья у него получаются уж слишком большие. Помогите Манао определить минимальное возможное количество вершин в искомом дереве делителей.
Первая строка содержит единственное целое число n (1 ≤ n ≤ 8). Во второй строке через пробел записаны n различных целых чисел ai (2 ≤ ai ≤ 1012).
Выведите единственное число — минимальное количество вершин в дереве делителей, содержащем каждое из чисел ai.
2
6 10
7
4
6 72 8 4
12
1
7
1
Пример 1. Самое маленькое дерево делителей выглядит так: 
Пример 2. В этом случае можно построить следующее дерево делителей: 
Пример 3. Дерево может состоять из единственной вершины.
