1. 

/**
* FWP: Ausgewaehlte Probleme aus dem ACM (SS10)
*
* Method: number theory
* Problem: 10780 - Again Prime? No Time
* Accepted: 0.368
* @author Evgeni Pavlidis
*
*/

import java.io.*;
import java.util.*;

class Main {

public static final int MAX = 5000;
public static final int[][] primeDivisor = new int[MAX+1][5];
public static final int[][] primePower = new int[MAX+1][5];
public static final int[] index = new int[MAX+1];


private static void findBaseDivisors()
{
int power,d;
// sieve the multiples of 2
for(int i = 2; i <= MAX; i+=2)
{
d = 2;
power = 1;
while((i % (d*2)) == 0)
{
d *= 2;
power++;
}
primePower[i][index[i]] = power;
primeDivisor[i][index[i]++] = 2;
}

// sieve other numbers
for(int i = 3; i <= MAX; i+=2)
if(index[i] == 0)
for(int j = i; j <= MAX; j += i)
{
d = i;
power = 1;
while(j % (d*i) == 0)
{
d *= i;
power++;
}
primePower[j][index[j]] = power;
primeDivisor[j][index[j]++] = i;
}
}

public static void main(String...args)
{
Scanner scanner = new Scanner(System.in);

int testCases = scanner.nextInt();
int m, n, divisor, current;

findBaseDivisors();

for(int c = 1; c <= testCases; c++)
{
int result = Integer.MAX_VALUE;
m = scanner.nextInt();
n = scanner.nextInt();

for(int i = 0; i < index[m]; i++)
{
current = 0;
divisor = primeDivisor[m][i];

while( n / divisor > 0)
{
current += n / divisor;
divisor *= primeDivisor[m][i];
}

current = current / primePower[m][i];

if(current < result)
result = current;

}

System.out.printf("Case %d:\n", c);
if(result == 0)
System.out.println("Impossible to divide");
else
System.out.println(result);
}
}
}