НСД
НСД (найбільший спільний дільник) набору чисел це найбільше число, на яке діляться усі числа заданого набору.
Алгоритм обчислення НСД з відніманням (алгоритм Евкліда): вибираються два ненульових числа з заданого набору, і більше число міняється різницею більшого і меншого. Ця операція повторюється, поки у наборі залишається не менше двох ненульових чисел.
Якщо усі числа, кріме одного, стали рівні 0, то алгоритм завершується, а ненульове число, що залишилось, і є НСД заданого набору.
Один крок алгоритму: вибір двох ненульових чисел з заданого набору і заміна більшого різницею. Існує багато стратегій вибору на черговому кроці пари чисел. При цьому кількість кроків у різних стратегіях буде різною.
Потрібно написати програму, яка визначає мінімальну кількість кроків при обчисленні НСД віднімання для заданого набору чисел.
Вхідні дані
Містить декілька (до 1000) тестів. Кожен тест записано в окремому рядку і починається з кількості чисел у наборі n (n ≤ 4). Далі у рядку йдуть n чисел заданого набору A[1] A[2] ... A[n] (1 ≤ A[i] ≤ 50).
Завершення тестів - число 0 у окремому рядку.
Вихідні дані
Для кожного тесту виведіть в окремому рядку мінімально можливу кількість кроків для знаходження НСД.