Козак Вус і НСД#134

Козак Вус і НСД

Сьогодні Козак Вус зустрівся зі своїм давнім другом — Козаком Вухом. Вони дуже довго розмовляли, згадували своє дитинство та юність. Так і зайшла мова про задачу, яку колись вони не змогли вирішити на олімпіаді з програмування.

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

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

Input

Перший рядок містить одне ціле число (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) "— числа масиву.

Output

Для кожного тесту в окремому рядку виведіть одне число — мінімальну кількість операцій, які необхідно виконати для того, щоб масив задовольняв дані умови.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Note

У першому прикладі можна перше та друге число збільшити до , тоді найбільший спільний дільник чисел з масиву буде рівний два.

У першому тесті другого прикладу можна усі числа зробити рівними .

У другому тесті другого прикладу масив можна змінити до масиву [4, 4, 8, 16, 16].

Scoring

№

Обмеження

Додаткові обмеження

Бали

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