#include<iostream>
#include<cmath>
using namespace std;

unsigned long long times[120],maxn=0,n;

int main()
{
    string s;
    cin>>s>>n;
    if(s.length()<n)
    {
        cout<<0;
        return 0;
    }
    for(int i=0;i<s.length();i++)
    {
        times[int(s[i])]++;
    }
    for(int i=0;i<127;i++)
    {
        if(times[i]>maxn)
        {
            maxn=times[i];
        }
    }
    long long already=n-s.length(),ans=0;
    for(int i=0;i<127;i++)
    {
        if(pow(maxn,i)+s.length()>=already)
        {
            ans=i;
            break;
        }
    }
    cout<<ans<<endl;
    return 0;
}