{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"GCD (greatest common divisor) of the set of numbers is the largest number to which all the numbers of a given set are divisible.\r\n\r\nAlgorithm for calculating GCD with subtractions (Euclid\u0027s 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.\r\n\r\nIf 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.\r\n\r\nOne 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.\r\n\r\nWrite a program that determines the minimum number of steps to calculate the GCD for a given set of numbers using subtract operation.\r\n\r\n#### Input\r\nContains 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**).\r\n\r\nThe end of the tests indicated the number **0** in a separate line.\r\n\r\n#### Output\r\nFor each test case print in a separate line the minimum possible number of steps to find the **GCD**."}},{"title":"Example","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e1 32\n2 2 4\n4 1 2 3 4 \n3 2 3 9\n3 3 6 6\n4 6 8 3 7\n4 43 50 50 50\n2 50 49\n4 50 1 1 1\n0\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0\n2\n6\n6\n3\n8\n14\n50\n52\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}