GCD#4896
The greatest common divisor (GCD) of a set of numbers is the largest integer that divides all the numbers in the given set.
Euclid's algorithm for GCD using subtraction is described as follows: select two nonzero numbers from the current set, then replace the larger number with the difference between the larger and the smaller. Repeat this operation while there are at least two nonzero numbers remaining in the set.
If, at any point, all numbers except one become equal to , the algorithm terminates. The remaining nonzero number is the GCD of the initial set.
One step of the algorithm is the process of choosing two nonzero numbers from the current set and replacing the larger with their difference. There are multiple strategies for selecting the pair of numbers at each step. The total number of steps depends on the chosen strategy, and may vary.
Your task is to write a program that determines the minimum possible number of steps required to compute the GCD for the given set using the subtraction operation.
The input consists of several (up to ) test cases. Each test is given on a separate line. Each line starts with an integer (n \leq 4) --- the number of elements in the set, followed by integers A_1, A_2, \ldots, A_n (1 \leq A_i \leq 50), representing the set.
The end of input is indicated by a single on a line.
For each test case, output on a separate line the minimum possible number of steps required to find the GCD.
Example 1