rt

#include <bits/stdc++.h>
#define int long long
using namespace std;

struct node
{
	int a[1010];
	void read()
	{
		string s;
		cin >> s;
		a[0] = s.size ();
		for (int i = 1; i <= a[0]; i++)
			a[i] = s[a[0] - i] - '0';
	}
	void print()
	{
		for (int i = a[0]; i >= 1; i--) cout << a[i];
	}
};

map <node, bool> mp;

int k;

node operator * (node a, node b)
{
	node c;
	c.a[0] = a.a[0] + b.a[0];
	for (int i = 1; i <= a.a[0]; i++)
		for (int j = 1; j <= b.a[0]; j++)
			c.a[i + j - 1] += a.a[i] * b.a[j];
	for (int i = 1; i <= c.a[0]; i++)
		c.a[i + 1] += c.a[i] / 10, c.a[i] %= 10;
	while (c.a[c.a[0] + 1]) c.a[0]++;
	while (c.a[0] > k) c.a[c.a[0]] = 0, c.a[0]--;
	return c;
}

signed main()
{
	node a;
	a.read ();
	cin >> k;
	
	node tep = a;
	while (!mp[tep])
	{
		mp[tep] = true;
		tep = tep * a;
	}
	cout << mp.size () << endl;
	return 0;
}