NSD#4896

NSD

1 saniyə

128 meqabayt

Çətin

Ən böyük ortaq bölən (ƏBOB) verilmiş ədədlər dəstinin bütün ədədlərini bölən ən böyük tam ədəddir.

ƏBOB-un çıxma əməliyyatı ilə hesablanması üçün Evklid alqoritmi belə təsvir olunur: cari dəstdən iki sıfırdan fərqli ədəd seçin, daha böyük ədədi onların fərqi ilə əvəz edin. Bu əməliyyatı, dəstdə ən azı iki sıfırdan fərqli ədəd qaldığı müddətdə təkrarlayın.

Əgər hansısa bir anda bütün ədədlərdən başqa yalnız biri sıfıra bərabər olarsa, alqoritm başa çatır. Qalan sıfırdan fərqli ədəd başlanğıc dəstin ƏBOB-u olur.

Alqoritmin bir addımı — cari dəstdən iki sıfırdan fərqli ədəd seçib, daha böyüyü onların fərqi ilə əvəz etməkdir. Hər addımda cütlüklərin seçilməsində fərqli strategiyalar mövcuddur. Ümumi addım sayı seçilmiş strategiyadan asılı olaraq fərqlənə bilər.

Sizin vəzifəniz — çıxma əməliyyatı ilə verilmiş dəst üçün ƏBOB tapmaq üçün lazım olan minimal mümkün addım sayını müəyyən edən proqram tərtib etməkdir.

Giriş

Girişdə bir neçə (maksimum $1000$ ) test verilir. Hər test ayrılıqda bir sətirdə verilir. Hər sətir əvvəlcə $n$ ( $n \leq 4$ n \leq 4) — dəstdəki ədədlərin sayını, sonra isə $n$ tam ədəd $A_{1}, A_{2}, \dots, A_{n}$ A_1, A_2, \ldots, A_n ( $1 \leq A_{i} \leq 50$ 1 \leq A_i \leq 50) verir.

Girişin sonu ayrıca bir sətrdə $0$ ilə göstərilir.

Çıxış

Hər test üçün ayrıca bir sətrdə ƏBOB tapmaq üçün mümkün minimal addım sayını çıxarın.

Nümunələr

Nümunə 1

Loading

n \leq 4

A_{1}, A_{2}, \dots, A_{n}

1 \leq A_{i} \leq 50