НСД
НСД
НСД (найбільший спільний дільник) набору чисел це найбільше число, на яке діляться усі числа заданого набору.
Алгоритм обчислення НСД з відніманням (алгоритм Евкліда): вибираються два ненульових числа з заданого набору, і більше число міняється різницею більшого і меншого. Ця операція повторюється, поки у наборі залишається не менше двох ненульових чисел.
Якщо усі числа, кріме одного, стали рівні 0, то алгоритм завершується, а ненульове число, що залишилось, і є НСД заданого набору.
Один крок алгоритму: вибір двох ненульових чисел з заданого набору і заміна більшого різницею. Існує багато стратегій вибору на черговому кроці пари чисел. При цьому кількість кроків у різних стратегіях буде різною.
Потрібно написати програму, яка визначає мінімальну кількість кроків при обчисленні НСД віднімання для заданого набору чисел.
Вхідні дані
Містить декілька (до 1000) тестів. Кожен тест записано в окремому рядку і починається з кількості чисел у наборі n (n ≤ 4). Далі у рядку йдуть n чисел заданого набору A1 A2 ... An (1 ≤ Ai ≤ 50).
Завершення тестів - число 0 у окремому рядку.
Вихідні дані
Для кожного тесту виведіть в окремому рядку мінімально можливу кількість кроків для знаходження НСД.
1 32 2 2 4 4 1 2 3 4 3 2 3 9 3 3 6 6 4 6 8 3 7 4 43 50 50 50 2 50 49 4 50 1 1 1 0
0 2 6 6 3 8 14 50 52