// Aizu 2086: !
// 2017.9.22 bal4u@uu

#include <stdio.h>

int pm[11] = {2,3,5,7,11,13,17,19,23,29,31};
int base[38][4], exp[38][4], len[38];

int main()
{
	int n, i, j, k, a, b;
	char ms[15], *p;
	long long m, ans, x, y;

	for (i = 2; i <= 36; i++) {
		for (j = 0; j < 11; j++) {
			if ((a = pm[j]) > i) break;
			if (i % a == 0) {
				b = i, k = 0; while (b % a == 0) b /= a, k++;
				base[i][len[i]] = a, exp[i][len[i]++] = k;
			}
		}
	}
#if 0
	for (i = 2; i <= 36; i++) {
		printf("%2d:", i);
		for (j = 0; j < len[i]; j++) printf(" %d(%d)", base[i][j], exp[i][j]);
		printf("\n");
	}
#endif

	while (scanf("%d%s", &n, &ms) && n) {
		m = 0, p = ms; while (*p) {
			m *= n, m += ((*p >= 'A') ? *p-'A'+10 : *p-'0');
			p++;
		}
		for (ans = (1LL << 62), i = 0; i < len[n]; i++) {
			x = m, a = base[n][i], y = 0;
			while (x /= a) y += x;
			y /= exp[n][i];	if (y < ans) ans = y;
		}
		printf("%lld\n", ans);
	}
	return 0;
}