Задача Gcdarray. Дано масив з n чисел. За один хід можна одне з чисел збільшити на 1. Вам необхідно з’ясувати, за яку мінімальну кількість операцій можливо отримати масив, який буде задовільняти умови:
- ai ⩽ ai+1 для всiх i вiд 1 до n – 1
- найбільший спільний дільник усіх чисел більший за 1.
Найбільший спільний дільник множини додатних чисел — це найбільше додатне число, що одночасно є дільником усіх чисел з множини.
Технічні умови. Програма Gcdarray читає з пристрою стандартного введення в першому рядку одне цiле число t (1 ⩽ t ⩽ 5) — кількість тестів. Далi читає t рядків, кожен з яких є описом відповідного тесту і мiстить цiле число n (1 ⩽ n ⩽ 104) — розмiр масиву а далі n цiлих чисел a1,a2,...,an (1 ⩽ ai ⩽ 104) — числа масиву. Всі числа розділено пропусками. Програма виводить на пристрій стандартного виведення рядок з t числами через пропуск, кожне з яких - мінімальна кількість операцій, яку необхідно виконати для того, щоб масив задовольняв даним умовам.
Приклади
|
Введення |
Виведення |
|
|
1 3 9 1 16 |
10 |
|
|
2 4 5 7 3 6 5 4 2 8 16 10 |
7 8 |
|
Примiтка
У першому прикладi можна перше та друге число збiльшити до 10, тодi найбiльший спiльний дiльник чисел з масиву буде становитиме 2
У першому тестi другого прикладу можна усi числа зробити рiвними 7.
У другому тестi другого прикладу масив можна змiнити до масиву [4,4,8,16,16].