У Васи скоро день рождения и мама решила подарить ему массив, состоящий из целых положительных чисел, a длины n.
Вася считает красотой массива наибольший общий делитель всех его элементов. Мама, конечно, хочет подарить ему максимально красивый массив (с наибольшей красотой). К сожалению, в магазине остался всего один массив a, но продавец сказал, что может уменьшить в нем некоторые числа, каждое число не более чем на k.
Продавец может из массива a получить массив b, если выполняются условия: bi > 0; 0 ≤ ai - bi ≤ k для всех 1 ≤ i ≤ n.
Помогите маме найти максимально возможную красоту массива, который она сможет подарить Васе (продавец сможет его получить).
Выходные данные
В единственной строке выведите целое число — максимально возможную красоту полученного массива.
Примечание
В первом примере можно получить массив:
3 6 9 12 12 15
Во втором примере можно получить следующий массив:
7 21 49 14 77
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6 1
3 6 10 12 13 16
|
3
|
|
2
|
5 3
8 21 52 15 77
|
7
|