#include<bits/stdc++.h>
using namespace std;
const int N=15;
int a[N];
vector<int> g[N];
bool st[N];
int ans=N;
int n;
bool check(vector<int> v,int i)
{
	for(auto x:v)
	{
		if(__gcd(a[x],a[i])>1) return false;//说明是互质的	
	}	
	return true;//说明是互质的 
} 
void dfs(int u,int cnt,int s) //组数,当前个数,起点 
{
	if(u>=ans) return ;
	if(cnt==n)
	{
		ans=u;
		return ;
	}
	bool flag=false;//还没有找到 
	for(int i=s;i<=n;i++)
	{
		if(!st[i]&&check(g[u],i))
		{
			st[i]=1;
			g[u].push_back(i);
			dfs(u,cnt+1,i+1);
			g[u].pop_back();
			st[i]=0;
			flag=true;
		}
	}
	if(!flag)
	{
		dfs(u+1,cnt,1);
	}
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	dfs(1,0,1);
	cout<<ans;
	return 0;
}