rt，码风新奇不喜勿喷

# pragma GCC optimize("Ofast,no-stack-protector")

# pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

# include <bits/stdc++.h>

typedef long long ll;

using namespace std;

const int maxn = 1e7;

int t;

ll k, n, sum, minx, tot, m, p[670000], cnt; //664579

bitset <10000005> vis;

int main () {

	ios::sync_with_stdio (0);

	cin.tie (0);

	cout.tie (0);

	for (int i = 2; i * i <= maxn; ++ i)
		if (! vis[i])
			for (int j = i * i; j <= maxn; j += i)
				vis[j] = 1;

	for (int i = 2; i <= maxn; ++ i)
		if (! vis[i])
			p[++ cnt] = i;
//	cerr << m << '\n';
	cin >> t;

	for (int ca = 1; ca <= t; ++ ca) {

		cin >> k >> n;

		cout << "Case " << ca << ": ";

		if (k == 1) {

			cout << "inf\n";

			continue ;

		}

		minx = 9223372036854775807ll;

		for (ll i = 1; i <= cnt && p[i] * p[i] <= k; ++ i)
			if (! (k % p[i])) {

				tot = sum = 0, m = n;

				while (! (k % p[i]))
					k /= p[i], ++ tot;

				while (m)
					m /= p[i], sum += m;

				minx = min (minx, sum / tot);

			}

		if (k ^ 1) {

			sum = 0;

			m = n;

			while (m)
				m /= k, sum += m;

			minx = min (minx, sum);

		}

		cout << minx << '\n';

	}

	return 0;

}