У вас есть массив целых положительных чисел a[1], a[2], ..., a[n], а также множество плохих простых чисел b1, b2, ..., bm. Простые числа, которые не встречаются в множестве b считаются хорошими. Красотой массива a назовем сумму 
, где функция f(s) определяется следующим образом:
- f(1) = 0;
- Пусть p — минимальный простой делитель числа s. Если p — хорошее простое число, то
, иначе 
.
Вам разрешено последовательно провести произвольное (возможно, ноль) количество операций улучшения массива a. Операцией улучшения назовем следующую последовательность действий:
- Выбрать некоторое число r (1 ≤ r ≤ n) и подсчитать значение g = НОД(a[1], a[2], ..., a[r]).
- Выполнить присвоения:
, 
, ..., 
.
Какую максимальную красоту массива вы сможете получить?
Выходные данные
Выведите единственное целое число — ответ на задачу.
Примечание
Обратите внимание, что ответ на задачу может быть отрицательным числом.
НОД(x1, x2, ..., xk) обозначает наибольшее целое положительное число, которое делит каждое xi без остатка.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 2
4 20 34 10 10
2 5
|
-2
|
|
2
|
4 5
2 4 8 16
3 5 7 11 17
|
10
|