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