#include <iostream>
using namespace std;

int main () {
  int S;
  cin >> S;
  for( int s=1; s<=S; s++ ){
    cout << "Scenario #" << s << ":" << endl;
    
    //--- Listen.
    int b, n;
    cin >> b >> n;
    
    //--- Dance...
    int m = 1<<30;
    for( int d=2; d<=b; d++ ){
      
      //--- Determine exponent of d in b.
      int e = 0;
      while( b % d == 0 ){
	b /= d;
	e++;
      }
      
      //--- Limit for d.
      if( e ){
	int N = n, M = 0;
	while( N ){
	  N /= d;
	  M += N;
	}
	m = min(m, M/e);
      }
    }
    
    //--- Answer.
    cout << m << endl << endl;
  }
}
