Задача Gcdarray. Дано масив з чисел. За один хід можна одне з чисел збільшити на 1. Вам необхідно з’ясувати, за яку мінімальну кількість операцій можливо отримати масив, який буде задовільняти  умови:

  • a⩽ ai+1                 для всiх вiд 1 до – 1
  • найбільший спільний дільник усіх чисел більший за 1.

Найбільший спільний дільник множини додатних чисел — це найбільше додатне число, що одночасно є дільником усіх чисел з множини.

Технічні умови. Програма Gcdarray  читає з пристрою стандартного введення в першому рядку  одне цiле число t  (1 ⩽ ⩽ 5) — кількість тестів.  Далi читає  t рядків, кожен з яких є описом відповідного  тесту  і мiстить  цiле число (1 ⩽ ⩽ 104) — розмiр масиву а далі цiлих чисел a1,a2,...,a(1 ⩽ a⩽ 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].

 

© LIKT 1998-2018