НСД#4896
Найбільший спільний дільник (НСД) набору чисел — це найбільше ціле число, на яке діляться всі числа із заданого набору.
Алгоритм Евкліда для знаходження НСД за допомогою віднімання описується так: виберіть два ненульових числа із поточного набору, потім замініть більше число на різницю між більшим та меншим. Повторюйте цю операцію, доки у наборі залишаються принаймні два ненульових числа.
Якщо у якийсь момент усі числа, окрім одного, стануть рівні , алгоритм завершується. Залишене ненульове число — це і є НСД початкового набору.
Один крок алгоритму — це вибір двох ненульових чисел з поточного набору та заміна більшого на їх різницю. Існує багато стратегій вибору пари на кожному кроці. Загальна кількість кроків залежить від вибраної стратегії і може відрізнятися.
Ваше завдання — написати програму, яка визначає мінімально можливу кількість кроків, необхідних для обчислення НСД для даного набору, використовуючи операцію віднімання.
Вхідні дані містять декілька (до ) тестів. Кожен тест задається окремим рядком. У кожному рядку спочатку дано ціле число (n \leq 4) — кількість чисел у наборі, потім цілих чисел A_1, A_2, \ldots, A_n (1 \leq A_i \leq 50), що складають набір.
Кінець вхідних даних позначається окремим рядком, що містить .
Для кожного тесту виведіть в окремому рядку мінімально можливу кількість кроків, необхідну для знаходження НСД.
Приклад 1