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

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

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

• $a_i\le a_{i+1}$ для всіх $i$ від $1$ до $n-1$.

• найбільший спільний дільник усіх чисел більший за $1$.

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

Input

Перший рядок містить одне ціле число $t$ $(1\le t\le 5)$ "— кількість тестів. Далі слідує опис кожного тесту.

Перший рядок опису кожного тесту містить одне ціле число $n$ ($1\le n\le 10^4$) "— розмір масиву.

Другий рядок опису кожного тесту містить $n$ цілих чисел $a_1,a_2,\dots ,a_n$ $(1\le a_i\le 10^4)$ "— числа масиву.

Output

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

Examples

Note

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

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

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

Scoring