春节前夕，米奇在钟楼上捡到了一台的复读机，这台复读机不仅可以自动复读，还可以用来求一个数列中所有数的最大公约数。
每次，米奇可以选择相邻的两个数 $a_i a_{i+1}$，并向机器中投入恰好为这两个数的和的金币，也即 $a_i + a_{i+1}$。然后，机器就会自动计算出这两个数字的最大公因数，并用它替换这两个相邻的数，替换的位置为这两个数的位置。反复执行这个操作，直到机器中的数列只剩下一个数，这个数就是答案。
正所谓不想当复读机修理工的有钱鼠不是好数学家，米奇想知道，至少使用多少个金币，才能算出答案。
一行一个整数，表示最小使用的金币数。