题目描述

给你一个长度为$n$的数组。你可以操作任意次，每次操作都在数组中选择两个数a，b，让a，b都除以他们的最大公约数。问最少操作几次可以使整个数组的最大公约数为1.

输入

第一行输入$n$ ($2$ $≤$ $n$ $≤$ $100000$)第二行$n$个整数$ai$（$1$ $≤$ $ai$ $≤$ $100000$）。

输出

输出一个整数$x$代表最终答案。

样例

2
2 2

1