НОД - Задачи

НОД (наибольший общий делитель) набора чисел это наибольшее число, на которое делятся все числа данного набора.

Алгоритм вычисления НОД c вычитаниями (алгоритм Евклида): выбираются два ненулевых числа из исходного набора, и большее число заменяется разностью большего и меньшего. Эта операция повторяется, пока в наборе остаётся не менее двух ненулевых чисел.

Если все числа, кроме одного, стали равны 0, то алгоритм завершается, а оставшееся ненулевое число и есть НОД исходного набора.

Один шаг алгоритма: выбор двух ненулевых чисел из исходного набора и замена большего разностью. Существует много стратегий выбора на очередном шаге пары чисел. При этом количество шагов при разных стратегиях будет различным.

Требуется написать программу, определяющую минимальное количество шагов при вычислении НОД вычитаниями для данного набора чисел.

Входные данные

Содержит несколько (до 1000) тестов. Каждый тест записан в отдельной строке и начинается с количества чисел в наборе n (n ≤ 4). Далее в строке идут n чисел исходного набора A₁ A₂ ... A_n (1 ≤ A_i ≤ 50).

Окончание тестов - число 0 в отдельной строке.

Выходные данные

Для каждого теста выведите ответ в отдельной строке минимально возможное количество шагов для нахождения НОД.

Лимит времени 1 секунда

Лимит использования памяти 128 MiB

Входные данные #1

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

Выходные данные #1

Источник 2005 Петрозаводск, SPb ETU Contest, Август 25, Задача E