#include <stdio.h>
#pragma warning (disable:4996)
#define min(a, b) ((a)<(b)?(a):(b))

int d[1001];

int main()
{
    int n, i, j;
    scanf("%d", &n);
    d[1] = 0;
    d[2] = 1;
    for (i =  3; i <= n; i++)
    {
        d[i] = 999999;
        for (j = 1; j < i; j++)
            d[i] = min(d[i],d[j] + d[i-j] + 1);
        for (j = 2; j < i; j++)
            if (i % j == 0)
                d[i] = min(d[i], d[i/j] + d[j]);
    }
    printf("%d\n", d[n]);
    return 0;
}

#include<iostream.h>
int max1(int *x,int *y,int i,int j)
{
    int k,m1=0,r=-1;bool p=true;
    for(k=i+1;k<=j&&p&&r==-1;k++)
        if(x[k]>=x[i])
        {
            m1=y[k];
            r=k;
            p=false;
        }
        if(r!=-1){
        for(k=r;k<=j;k++)
            if(x[k]>=x[i] && y[k]>=m1)
                m1=y[k];

            return m1+1;
        }
        return -1;
}
int main()
{
    int n,a[1005],i,l[1005],max;
    cin>>n;
    for(i=1;i<=n;i++)
        cin>>a[i];
    l[n]=1;
    if(a[n-1]>a[n])
        l[n-1]=1;
    else
        l[n-1]=2;
    for(i=n-2;i>=1;i--)
        l[i]=max1(a,l,i,n);
    max=l[1];
    for(i=2;i<=n;i++)
        if(l[i]>max)
            max=l[i];
        cout<<max;
return 0;
}

#include<iostream.h>

int f(int k,int c,char *s)
{
    if(k==0&&c==0)
        return 1;
    else
        if(k==0&&c>0)
            return 0;
        else
            if(k>=0 && c==-1)
                return 0;
            else
            {
                if(s[k]=='(')
                    return f(k-1,c-1,s);
                else
                if(s[k]==')')
                    return f(k-1,c+1,s);
                else
                        if(s[k]=='?')
                    return f(k-1,c-1,s)+f(k-1,c+1,s);

            }
}
int main()
{
    int n,i=1;
    char s[1000];

    while(cin>>s[i])
    {
        i++;
    }
cout<<f(i-1,0,s);
    return 0;
}