GCD (greatest common divisor) of the set of numbers is the largest number to which all the numbers of a given set are divisible.
Algorithm for calculating GCD with subtractions (Euclid's algorithm): two non-zero numbers from the original set are selected, and a larger number is replaced by a difference of the larger and the smaller. This operation is repeated until there are at least two non-zero numbers in the set.
If all numbers except one are equal to 0, then the algorithm is completed, and the remaining nonzero number is the GCD of the initial set.
One step of the algorithm: choose two nonzero numbers from the current set and replace the larger with a difference. There are many strategies to choose the pair of numbers on the next step. In this case the number of steps for different strategies will be different.
Write a program that determines the minimum number of steps to calculate the GCD for a given set of numbers using subtract operation.
Contains some (up to 1000) tests. Each test is given in a separate line and starts with the amount of numbers n (n ≤ 4) in the set. Then line contains n integers of the given set A[1] A[2]
... A[n]
(1 ≤ A[i]
≤ 50).
The end of the tests indicated the number 0 in a separate line.
For each test case print in a separate line the minimum possible number of steps to find the GCD.