//BISMILLAHIRRAHMANIRRAHIM
/*
manus tar shopner soman boro
all my suceesses are dedicated to my parents
The true test of a man's character is what he does when no one is watching.
Author :: Shakil Ahmed
.............AUST_CSE27.........
prob ::
Type ::
verdict::
*/
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
// Macro
#define eps 1e-9
#define pi acos(-1.0)
#define ff first
#define ss second
#define re return
#define QI queue<int>
#define SI stack<int>
#define SZ(x) ((int) (x).size())
#define all(x) (x).begin(), (x).end()
#define sq(a) ((a)*(a))
#define distance(a,b) (sq(a.x-b.x) + sq(a.y-b.y))
#define iseq(a,b) (fabs(a-b)<eps)
#define eq(a,b) iseq(a,b)
#define ms(a,b) memset((a),(b),sizeof(a))
#define G() getchar()
#define MAX3(a,b,c) max(a,max(b,c))
#define II ( { int a ; read(a) ; a; } )
#define LL ( { Long a ; read(a) ; a; } )
#define DD ({double a; scanf("%lf", &a); a;})
double const EPS=3e-8;
using namespace std;
#define FI freopen ("input.txt", "r", stdin)
#define FO freopen ("output.txt", "w", stdout)
typedef long long Long;
typedef long long int64;
typedef unsigned long long ull;
typedef vector<int> vi ;
typedef set<int> si;
typedef vector<Long>vl;
typedef pair<int,int>pii;
typedef pair<string,int>psi;
typedef pair<Long,Long>pll;
typedef pair<double,double>pdd;
typedef vector<pii> vpii;
// For loop
#define forab(i, a, b) for (__typeof (b) i = (a) ; i <= b ; ++i)
#define rep(i, n) forab (i, 0, (n) - 1)
#define For(i, n) forab (i, 1, n)
#define rofba(i, a, b) for (__typeof (b)i = (b) ; i >= a ; --i)
#define per(i, n) rofba (i, 0, (n) - 1)
#define rof(i, n) rofba (i, 1, n)
#define forstl(i, s) for (__typeof ((s).end ()) i = (s).begin (); i != (s).end (); ++i)
template< class T > T gcd(T a, T b) { return (b != 0 ? gcd<T>(b, a%b) : a); }
template< class T > T lcm(T a, T b) { return (a / gcd<T>(a, b) * b); }
//Fast Reader
template<class T>inline bool read(T &x){int c=getchar();int sgn=1;while(~c&&c<'0'||c>'9'){if(c=='-')sgn=-1;c=getchar();}for(x=0;~c&&'0'<=c&&c<='9';c=getchar())x=x*10+c-'0'; x*=sgn; return ~c;}
//int dx[]={1,0,-1,0};int dy[]={0,1,0,-1}; //4 Direction
//int dx[]={1,1,0,-1,-1,-1,0,1};int dy[]={0,1,1,1,0,-1,-1,-1};//8 direction
//int dx[]={2,1,-1,-2,-2,-1,1,2};int dy[]={1,2,2,1,-1,-2,-2,-1};//Knight Direction
//int dx[]={2,1,-1,-2,-1,1};int dy[]={0,1,1,0,-1,-1}; //Hexagonal Direction
/* ************************************** My code start here ****************************************** */
const int NX = 2e6 + 10 ;
int check[ NX ] , id , inp[ NX ] , ID[ NX ] ;
Long prime[ NX ] ;
void ini()
{
int i , j ;
id = 0 ;
prime[ id++ ] = 2 ;
ID[ 2 ] = id ;
check[ 1 ] = -1 ;
check[ 2 ] = 1 ;
//for ( int i = 4 ; i < NX ; i += 2 ) check[i] = -1 ;
// int i ;
for ( i = 3 ; i * i < NX ; i += 2 )
{
if( check[i] == 0 )
{
prime[ id++ ] = i ;
ID[ i ] = id ;
check[ i ] = 1 ;
for ( int j = i * i ; j < NX ; j += ( i + i ) ) check[ j ] = -1 ;
}
}
while( i < NX )
{
if( check[i] == 0 )
{
check[i] = 1 ;
prime[id++] = i ;
ID[ i ] = id ;
}
i += 2 ;
}
/* for ( int i = 1 ; i <= 50 ; i++ )
{
if( check[i] == 1 ) printf(" %d -> %d\n" , i , ID[i] );
} */
}
int n ; Long dp[ 505 ][ 505 ];
Long binary( int val )
{
int low = 0 , high = id - 1 , mid ;
Long ans = ( 1e16) ;
while( low <= high )
{
int mid = ( low + high )/2 ;
if( prime[ mid ] < val )
{
ans = prime[ mid ];
low = mid + 1 ;
}
else high = mid - 1 ;
}
return ans ;
}
Long Cal( int x , int y )
{
// special case
//if( inp[ y ] == 2 && inp[ x ] == 1 ) return ( 3 );
//if( inp[x] == 2 && inp[y] == 1 ) return ( 3 );
if( check[ inp[x] ] == 1 && check[ inp[y]] == 1 )
{
if( ID[ inp[y] ] - ID[ inp[ x ] ] == 1 ) return 1 ;
}
if( inp[ y ] > inp[ x ] )
{
Long A = binary( inp[y] ) ;
if( A < inp[x] || A == ( 1e16) )
{
int p = lower_bound( prime , prime + id , inp[x] ) - prime ;
Long a = prime[ p ] - inp[ x ];
p = lower_bound ( prime , prime + id , prime[ p ] + 1 ) - prime ;
Long b = prime[ p ] - inp[ y ];
return a + b ;
}
A -= inp[ x ];
int p = lower_bound( prime , prime + id , inp[y] ) - prime ;
A = A + ( prime[p] - inp[y] ) ;
return A ;
}
int p = lower_bound( prime , prime + id , inp[x] ) - prime ;
Long a = prime[ p ] - inp[ x ];
p = lower_bound ( prime , prime + id , prime[ p ] + 1 ) - prime ;
Long b = prime[ p ] - inp[ y ];
return a + b ;
}
Long DP( int x , int y )
{
if( x > y ) return 0 ;
if( x + 1 == y )
{
return Cal( x , y ) + 1;
}
Long &ret = dp[ x ][ y ];
if( ret != -1 ) return ret ;
ret = Cal( x , y ) + DP( x + 1 , y - 1 ) + 1;
int i ;
for ( i = x + 1 ; i < y - 1 ; i+=2 )
{
ret = min( ret , Cal( x , i ) + DP( x + 1 , i - 1 ) + DP( i + 1 , y ) + 1 );
}
return ret ;
}
int main()
{
// I will always use scanf and printf
// May be i won't be a good programmer but i will be a good human being
ini();
//for ( int i = 4 ; i <= 30 ; i += 4 ) cout << binary( i ) << endl ;
/* int p = lower_bound( prime , prime + id , 4 ) - prime ;
cout << prime[ p ] << endl ;
p = lower_bound( prime , prime + id , 5 ) - prime ;
cout << prime[p] << endl ; */
while( scanf("%d",&n) == 1)
{
ms( dp , -1 );
rep( i , n ) inp[ i ] = II ;
printf("%lld\n",DP( 0 , n - 1 ) );
}
return 0;
}
Ly9CSVNNSUxMQUhJUlJBSE1BTklSUkFISU0KLyoKIG1hbnVzIHRhciBzaG9wbmVyIHNvbWFuIGJvcm8KIGFsbCBteSBzdWNlZXNzZXMgYXJlIGRlZGljYXRlZCB0byBteSBwYXJlbnRzCiBUaGUgdHJ1ZSB0ZXN0IG9mIGEgbWFuJ3MgY2hhcmFjdGVyIGlzIHdoYXQgaGUgZG9lcyB3aGVuIG5vIG9uZSBpcyB3YXRjaGluZy4KCgogQXV0aG9yIDo6IFNoYWtpbCBBaG1lZAouLi4uLi4uLi4uLi4uQVVTVF9DU0UyNy4uLi4uLi4uLgogcHJvYiAgIDo6CiBUeXBlICAgOjoKIHZlcmRpY3Q6OgogKi8KCiNpbmNsdWRlIDxiaXRzL3N0ZGMrKy5oPgojZGVmaW5lIHBiIHB1c2hfYmFjawojZGVmaW5lIG1wIG1ha2VfcGFpcgoKLy8gTWFjcm8KI2RlZmluZSBlcHMgMWUtOQojZGVmaW5lIHBpIGFjb3MoLTEuMCkKI2RlZmluZSBmZiBmaXJzdAojZGVmaW5lIHNzIHNlY29uZAojZGVmaW5lIHJlIHJldHVybgojZGVmaW5lIFFJIHF1ZXVlPGludD4KI2RlZmluZSBTSSBzdGFjazxpbnQ+CiNkZWZpbmUgU1ooeCkgKChpbnQpICh4KS5zaXplKCkpCiNkZWZpbmUgYWxsKHgpICh4KS5iZWdpbigpLCAoeCkuZW5kKCkKI2RlZmluZSBzcShhKSAoKGEpKihhKSkKI2RlZmluZSBkaXN0YW5jZShhLGIpIChzcShhLngtYi54KSArIHNxKGEueS1iLnkpKQojZGVmaW5lIGlzZXEoYSxiKSAoZmFicyhhLWIpPGVwcykKI2RlZmluZSBlcShhLGIpIGlzZXEoYSxiKQojZGVmaW5lIG1zKGEsYikgbWVtc2V0KChhKSwoYiksc2l6ZW9mKGEpKQojZGVmaW5lIEcoKSBnZXRjaGFyKCkKI2RlZmluZSBNQVgzKGEsYixjKSBtYXgoYSxtYXgoYixjKSkKI2RlZmluZSBJSSAoIHsgaW50IGEgOyByZWFkKGEpIDsgYTsgfSApCiNkZWZpbmUgTEwgKCB7IExvbmcgYSA7IHJlYWQoYSkgOyBhOyB9ICkKI2RlZmluZSBERCAoe2RvdWJsZSBhOyBzY2FuZigiJWxmIiwgJmEpOyBhO30pCgpkb3VibGUgY29uc3QgRVBTPTNlLTg7CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgojZGVmaW5lIEZJIGZyZW9wZW4gKCJpbnB1dC50eHQiLCAiciIsIHN0ZGluKQojZGVmaW5lIEZPIGZyZW9wZW4gKCJvdXRwdXQudHh0IiwgInciLCBzdGRvdXQpCgp0eXBlZGVmIGxvbmcgbG9uZyBMb25nOwp0eXBlZGVmIGxvbmcgbG9uZyBpbnQ2NDsKdHlwZWRlZiB1bnNpZ25lZCBsb25nIGxvbmcgdWxsOwp0eXBlZGVmIHZlY3RvcjxpbnQ+IHZpIDsKdHlwZWRlZiBzZXQ8aW50PiBzaTsKdHlwZWRlZiB2ZWN0b3I8TG9uZz52bDsKdHlwZWRlZiBwYWlyPGludCxpbnQ+cGlpOwp0eXBlZGVmIHBhaXI8c3RyaW5nLGludD5wc2k7CnR5cGVkZWYgcGFpcjxMb25nLExvbmc+cGxsOwp0eXBlZGVmIHBhaXI8ZG91YmxlLGRvdWJsZT5wZGQ7CnR5cGVkZWYgdmVjdG9yPHBpaT4gdnBpaTsKCi8vIEZvciBsb29wCgojZGVmaW5lIGZvcmFiKGksIGEsIGIpCWZvciAoX190eXBlb2YgKGIpIGkgPSAoYSkgOyBpIDw9IGIgOyArK2kpCiNkZWZpbmUgcmVwKGksIG4pCQlmb3JhYiAoaSwgMCwgKG4pIC0gMSkKI2RlZmluZSBGb3IoaSwgbikJCWZvcmFiIChpLCAxLCBuKQojZGVmaW5lIHJvZmJhKGksIGEsIGIpCWZvciAoX190eXBlb2YgKGIpaSA9IChiKSA7IGkgPj0gYSA7IC0taSkKI2RlZmluZSBwZXIoaSwgbikJCXJvZmJhIChpLCAwLCAobikgLSAxKQojZGVmaW5lIHJvZihpLCBuKQkJcm9mYmEgKGksIDEsIG4pCiNkZWZpbmUgZm9yc3RsKGksIHMpCWZvciAoX190eXBlb2YgKChzKS5lbmQgKCkpIGkgPSAocykuYmVnaW4gKCk7IGkgIT0gKHMpLmVuZCAoKTsgKytpKQoKdGVtcGxhdGU8IGNsYXNzIFQgPiBUIGdjZChUIGEsIFQgYikgeyByZXR1cm4gKGIgIT0gMCA/IGdjZDxUPihiLCBhJWIpIDogYSk7IH0KdGVtcGxhdGU8IGNsYXNzIFQgPiBUIGxjbShUIGEsIFQgYikgeyByZXR1cm4gKGEgLyBnY2Q8VD4oYSwgYikgKiBiKTsgfQoKLy9GYXN0IFJlYWRlcgp0ZW1wbGF0ZTxjbGFzcyBUPmlubGluZSBib29sIHJlYWQoVCAmeCl7aW50IGM9Z2V0Y2hhcigpO2ludCBzZ249MTt3aGlsZSh+YyYmYzwnMCd8fGM+JzknKXtpZihjPT0nLScpc2duPS0xO2M9Z2V0Y2hhcigpO31mb3IoeD0wO35jJiYnMCc8PWMmJmM8PSc5JztjPWdldGNoYXIoKSl4PXgqMTArYy0nMCc7IHgqPXNnbjsgcmV0dXJuIH5jO30KCi8vaW50IGR4W109ezEsMCwtMSwwfTtpbnQgZHlbXT17MCwxLDAsLTF9OyAvLzQgRGlyZWN0aW9uCi8vaW50IGR4W109ezEsMSwwLC0xLC0xLC0xLDAsMX07aW50IGR5W109ezAsMSwxLDEsMCwtMSwtMSwtMX07Ly84IGRpcmVjdGlvbgovL2ludCBkeFtdPXsyLDEsLTEsLTIsLTIsLTEsMSwyfTtpbnQgZHlbXT17MSwyLDIsMSwtMSwtMiwtMiwtMX07Ly9LbmlnaHQgRGlyZWN0aW9uCi8vaW50IGR4W109ezIsMSwtMSwtMiwtMSwxfTtpbnQgZHlbXT17MCwxLDEsMCwtMSwtMX07IC8vSGV4YWdvbmFsIERpcmVjdGlvbgoKLyogKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKiogIE15IGNvZGUgc3RhcnQgaGVyZSAqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKiogKi8KCgpjb25zdCBpbnQgTlggPSAyZTYgKyAxMCA7CgppbnQgY2hlY2tbIE5YIF0gLCBpZCAsIGlucFsgTlggXSAsIElEWyBOWCBdIDsKTG9uZyBwcmltZVsgTlggXSA7CnZvaWQgaW5pKCkKewogICAgaW50IGkgLCBqIDsKICAgIGlkID0gMCA7CiAgICBwcmltZVsgaWQrKyBdID0gMiA7CiAgICBJRFsgMiBdID0gaWQgOwogICAgY2hlY2tbIDEgXSA9IC0xIDsKICAgIGNoZWNrWyAyIF0gPSAxIDsKICAgIC8vZm9yICggaW50IGkgPSA0IDsgaSA8IE5YIDsgaSArPSAyICkgY2hlY2tbaV0gPSAtMSA7CiAgLy8gIGludCBpIDsKICAgIGZvciAoIGkgPSAzIDsgaSAqIGkgPCBOWCA7IGkgKz0gMiApCiAgICB7CiAgICAgICAgaWYoIGNoZWNrW2ldID09IDAgKQogICAgICAgIHsKICAgICAgICAgICAgcHJpbWVbIGlkKysgXSA9IGkgOwogICAgICAgICAgICBJRFsgaSBdID0gaWQgOwogICAgICAgICAgICBjaGVja1sgaSBdID0gMSA7CiAgICAgICAgICAgIGZvciAoIGludCBqID0gaSAqIGkgOyBqIDwgTlggOyBqICs9ICggaSArIGkgKSApIGNoZWNrWyBqIF0gPSAtMSA7CiAgICAgICAgfQogICAgfQogICAgd2hpbGUoIGkgPCBOWCApCiAgICB7CiAgICAgICAgaWYoIGNoZWNrW2ldID09IDAgKQogICAgICAgIHsKICAgICAgICAgICAgY2hlY2tbaV0gPSAxIDsKICAgICAgICAgICAgcHJpbWVbaWQrK10gPSBpIDsKICAgICAgICAgICAgSURbIGkgXSA9IGlkIDsKICAgICAgICB9CiAgICAgICAgaSArPSAyIDsKICAgIH0KICAgLyogZm9yICggaW50IGkgPSAxIDsgaSA8PSA1MCA7IGkrKyApCiAgICB7CiAgICAgICAgaWYoIGNoZWNrW2ldID09IDEgKSBwcmludGYoIiAlZCAtPiAlZFxuIiAsIGkgLCBJRFtpXSApOwogICAgfSAqLwoKfQppbnQgbiA7IExvbmcgZHBbIDUwNSBdWyA1MDUgXTsKTG9uZyBiaW5hcnkoIGludCB2YWwgKQp7CiAgICBpbnQgbG93ID0gMCAsIGhpZ2ggPSBpZCAtIDEgLCBtaWQgOwogICAgTG9uZyBhbnMgPSAoIDFlMTYpIDsKICAgIHdoaWxlKCBsb3cgPD0gaGlnaCApCiAgICB7CiAgICAgICAgaW50IG1pZCA9ICggbG93ICsgaGlnaCApLzIgOwogICAgICAgIGlmKCBwcmltZVsgbWlkIF0gPCB2YWwgKQogICAgICAgIHsKICAgICAgICAgICAgYW5zID0gcHJpbWVbIG1pZCBdOwogICAgICAgICAgICBsb3cgPSBtaWQgKyAxIDsKCiAgICAgICAgfQogICAgICAgIGVsc2UgaGlnaCA9IG1pZCAtIDEgOwogICAgfQogICAgcmV0dXJuIGFucyA7Cn0KTG9uZyBDYWwoIGludCB4ICwgaW50IHkgKQp7CiAgICAgICAgLy8gc3BlY2lhbCBjYXNlCiAgICAgICAgLy9pZiggaW5wWyB5IF0gPT0gMiAmJiBpbnBbIHggXSA9PSAxICkgcmV0dXJuICggMyApOwogICAgICAgIC8vaWYoIGlucFt4XSA9PSAyICYmIGlucFt5XSA9PSAxICkgcmV0dXJuICggMyApOwogICAgICAgIGlmKCBjaGVja1sgaW5wW3hdIF0gPT0gMSAmJiBjaGVja1sgaW5wW3ldXSA9PSAxICkKICAgICAgICB7CiAgICAgICAgICAgIGlmKCBJRFsgaW5wW3ldIF0gLSBJRFsgaW5wWyB4IF0gXSA9PSAxICkgcmV0dXJuIDEgOwogICAgICAgIH0KCiAgICAgICAgaWYoIGlucFsgeSBdID4gaW5wWyB4IF0gKQogICAgICAgIHsKICAgICAgICAgICAgTG9uZyBBID0gYmluYXJ5KCBpbnBbeV0gKSA7CiAgICAgICAgICAgIGlmKCBBIDwgaW5wW3hdIHx8IEEgPT0gKCAxZTE2KSApCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIGludCBwID0gbG93ZXJfYm91bmQoIHByaW1lICwgcHJpbWUgKyBpZCAsIGlucFt4XSApIC0gcHJpbWUgOwogICAgICAgICAgICAgICAgTG9uZyBhID0gcHJpbWVbIHAgXSAtIGlucFsgeCBdOwogICAgICAgICAgICAgICAgcCA9IGxvd2VyX2JvdW5kICggcHJpbWUgLCBwcmltZSArIGlkICwgcHJpbWVbIHAgXSArIDEgKSAtIHByaW1lIDsKICAgICAgICAgICAgICAgIExvbmcgYiA9IHByaW1lWyBwIF0gLSBpbnBbIHkgXTsKICAgICAgICAgICAgICAgcmV0dXJuIGEgKyBiIDsKICAgICAgICAgICAgfQogICAgICAgICAgICBBIC09IGlucFsgeCBdOwoKICAgICAgICAgICAgaW50IHAgPSBsb3dlcl9ib3VuZCggcHJpbWUgLCBwcmltZSArIGlkICwgaW5wW3ldICkgLSBwcmltZSA7CiAgICAgICAgICAgIEEgPSBBICsgKCBwcmltZVtwXSAtIGlucFt5XSApIDsKCiAgICAgICAgICAgIHJldHVybiBBIDsKICAgICAgICB9CgoKICAgICAgICBpbnQgcCA9IGxvd2VyX2JvdW5kKCBwcmltZSAsIHByaW1lICsgaWQgLCBpbnBbeF0gKSAtIHByaW1lIDsKICAgICAgICBMb25nIGEgPSBwcmltZVsgcCBdIC0gaW5wWyB4IF07CiAgICAgICAgcCA9IGxvd2VyX2JvdW5kICggcHJpbWUgLCBwcmltZSArIGlkICwgcHJpbWVbIHAgXSArIDEgKSAtIHByaW1lIDsKCiAgICAgICAgTG9uZyBiID0gcHJpbWVbIHAgXSAtIGlucFsgeSBdOwogICAgICAgIHJldHVybiBhICsgYiAgOwoKfQpMb25nIERQKCBpbnQgeCAsIGludCB5ICkKewogICAgaWYoIHggPiB5ICkgcmV0dXJuIDAgOwogICAgaWYoIHggKyAxID09IHkgKQogICAgewogICAgICAgIHJldHVybiBDYWwoIHggLCB5ICkgKyAxOwogICAgfQogICAgTG9uZyAmcmV0ID0gZHBbIHggXVsgeSBdOwogICAgaWYoIHJldCAhPSAtMSApIHJldHVybiByZXQgOwogICAgcmV0ID0gQ2FsKCB4ICwgeSApICsgRFAoIHggKyAxICwgeSAtIDEgKSArIDE7CiAgICBpbnQgaSA7CiAgICBmb3IgKCBpID0geCArIDEgOyBpIDwgeSAtIDEgIDsgaSs9MiApCiAgICB7CiAgICAgICAgcmV0ID0gbWluKCByZXQgLCBDYWwoIHggLCBpICkgKyBEUCggeCArIDEgLCBpIC0gMSApICsgRFAoIGkgKyAxICwgeSApICsgMSApOwogICAgfQogICAgcmV0dXJuIHJldCA7Cgp9CmludCBtYWluKCkKewogICAvLyBJIHdpbGwgYWx3YXlzIHVzZSBzY2FuZiBhbmQgcHJpbnRmCiAgIC8vIE1heSBiZSBpIHdvbid0IGJlIGEgZ29vZCBwcm9ncmFtbWVyIGJ1dCBpIHdpbGwgYmUgYSBnb29kIGh1bWFuIGJlaW5nCiAgICBpbmkoKTsKICAgIC8vZm9yICggaW50IGkgPSA0IDsgaSA8PSAzMCA7IGkgKz0gNCApIGNvdXQgPDwgYmluYXJ5KCBpICkgPDwgZW5kbCA7CiAgIC8qIGludCBwID0gbG93ZXJfYm91bmQoIHByaW1lICwgcHJpbWUgKyBpZCAsIDQgKSAtIHByaW1lIDsKICAgIGNvdXQgPDwgcHJpbWVbIHAgXSA8PCBlbmRsIDsKICAgIHAgPSBsb3dlcl9ib3VuZCggcHJpbWUgLCBwcmltZSArIGlkICwgNSApIC0gcHJpbWUgOwogICAgY291dCA8PCBwcmltZVtwXSA8PCBlbmRsIDsgKi8KICAgIHdoaWxlKCBzY2FuZigiJWQiLCZuKSA9PSAxKQogICAgewogICAgICAgIG1zKCBkcCAsIC0xICk7CiAgICAgICAgcmVwKCBpICwgbiApIGlucFsgaSBdID0gSUkgOwogICAgICAgIHByaW50ZigiJWxsZFxuIixEUCggMCAsIG4gLSAxICkgKTsKICAgIH0KCgoKCiAgICByZXR1cm4gMDsKfQo=