# 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;

int t;

ll k, n, sum, minx, tot, m;

int main () {

	ios::sync_with_stdio (0);

	cin.tie (0);

	cout.tie (0);

	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 = 2; i * i <= k; ++ i)
			if (! (k % i)) {

				tot = sum = 0, m = n;

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

				while (m)
					m /= 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;

}