#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int n;
int a[10000];
int b[10000];
int c[10000];
int v[60];
int d[60];
int ans;
int dis;
int now;

void dfs(int l)
{
	if(l==n+1)
	{   
	    dis=1;
		for(int i=1;i<=now;i++)
		if(b[i]!=-1)dis=0;
		return;
	}

	
	if(d[a[l]]==0)
	{		
	dfs(l+1);		
	return;		
    }

		
	int flat=0;	
	for(int i=1;i<=now;i++)
	{
		if(b[i]!=-1&&a[l]!=b[i])
		{
        int q=a[l]-b[i];
        
        if(b[i]-q>=0)continue; 
		 
        int dis2=0;
		for(int j=a[l]+q;j<=59;j+=q)
		{
			if(d[j]==0)
			{
				dis2=1;
				break;
			}
		}
		
			if(dis2==0)
			{
				for(int j=a[l];j<=59;j+=q)
				d[j]--;			    
			    int w=b[i];
				b[i]=-1;
				dfs(l+1);
				b[i]=w;				
				
			    for(int j=a[l];j<=59;j+=q)
				d[j]++;
			}
		}
	}
	
	
	
	if(a[l]<=29&&now+1<=ans)
	{
		now++;
		b[now]=a[l];	
		d[a[l]]--;
        dfs(l+1);
        d[a[l]]++;
        b[now]=0;
		now--;
	}
	return ;
}



int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
	scanf("%d",&a[i]);
	v[a[i]]++;
    }
    //sort(a+1,a+1+n);
	for(ans=1;ans<=17;ans++)
	{
	for(int i=0;i<=59;i++)
	d[i]=v[i];
	
	memset(b,0,sizeof(b));
	memset(c,0,sizeof(c));
	
	now=0;	
	dfs(1);
	if(dis)break;
    }
    if(ans==18)ans--;
    cout<<ans<<'\n';
	return 0;
}