Сьогодні Козак Вус зустрівся зі своїм давнім другом — Козаком Вухом. Вони дуже довго розмовляли, згадували своє дитинство та юність. Так і зайшла мова про задачу, яку колись вони не змогли вирішити на олімпіаді з програмування.
Дано масив з чисел. За один хід можна одне з чисел збільшити на . Вам необхідно з'ясувати, за яку мінімальну кількість операцій можливо отримати масив, який буде задовольняти такі умови:
a_i \le a_{i+1} для всіх від до n-1.
найбільший спільний дільник усіх чисел більший за .
Найбільший спільний дільник множини додатних чисел — це найбільше додатне число, що одночасно є дільником усіх чисел з множини.
Перший рядок містить одне ціле число (1\leq t\leq 5) "— кількість тестів. Далі слідує опис кожного тесту.
Перший рядок опису кожного тесту містить одне ціле число (1\leq n\leq 10^4) "— розмір масиву.
Другий рядок опису кожного тесту містить цілих чисел a_1, a_2, \ldots, a_n (1\leq a_i\leq 10^4) "— числа масиву.
Для кожного тесту в окремому рядку виведіть одне число — мінімальну кількість операцій, які необхідно виконати для того, щоб масив задовольняв дані умови.
Example 1
Example 2
У першому прикладі можна перше та друге число збільшити до , тоді найбільший спільний дільник чисел з масиву буде рівний два.
У першому тесті другого прикладу можна усі числа зробити рівними .
У другому тесті другого прикладу масив можна змінити до масиву [4, 4, 8, 16, 16].
№ | Обмеження | Додаткові обмеження | Бали |
1 | 1\leq n\leq 10^4 | Усі числа парні | 10 |
2 | 1\leq n\leq 10 | - | 20 |
3 | 1\leq n\leq 10^3 | - | 30 |
4 | 1\leq n\leq 10^4 | - | 40 |