给定整数 $n,m$ 请求出最大的整数 $k$ 使得 $m^k|n!$。

$n!=1\times 2\times \dots \times (n-1)\times n$

本题有多组数据。

输入格式

第一行一个整数 $t$ 表示数据的组数。

第二到 $t+1$ 行，输入两个整数 $m,n$。

输出格式

对于每一组数据，先输出 case x:，$x$ 表示当前的数据编号。

然后再输出每一组数据最大的 $k$，无解输出 Impossible to divide

数据

$1\le n<10000,1<m<5000,t\le 500$

translate by @fire_flame

给定整数 $n,m$ 请求出最大的整数 $k$ 使得 $m^k|n!$。

$n!=1\times 2\times \dots \times (n-1)\times n$

本题有**多组数据**。

## 输入格式

第一行一个整数 $t$ 表示数据的组数。

第二到 $t+1$ 行，输入两个整数 $m,n$。

## 输出格式

对于每一组数据，先输出 `case x:`，$x$ 表示当前的数据编号。

然后再输出每一组数据最大的 $k$，无解输出 `Impossible to divide`

## 数据

$1\le n<10000,1<m<5000,t\le 500$

translate by @fire_flame

@chen_zhe