GCD - Problems

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.

Input

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₁ A₂ ... A_n (1 ≤ A_i ≤ 50).

The end of the tests indicated the number 0 in a separate line.

Output

For each test case print in a separate line the minimum possible number of steps to find the GCD.

Time limit 1 second

Memory limit 128 MiB

Input example #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

Output example #1

Source 2005 Petrozavodsk, SPb ETU Contest, August 25, Problem E