NYOJ--56--阶乘因式分解（一）

/*
	Name: NYOJ--56--阶乘因式分解（一）
	Author: 日天大帝 
	Date: 20/04/17 20:45
	Description: 求n的阶乘，这个数字可能很大，所以换别的思路做
				n100,m=5，1-100中是5的倍数的有5、10、15……100，共20个，从这20个数中各分解出一个5
				，则有20个5，然后这20个数变成20、19、18……1，1-20中又能分解出4个5，
				再向下就不够5个数了，结束循环， 
*/
#include<iostream>
using namespace std;
int main(){
	ios::sync_with_stdio(false);
	
	int s;cin>>s;
	while(s--){
		int m,n,ct = 0;;
		cin>>m>>n;
		while(m >= n){
			ct += m/n;
			m /= n;
		}
		cout<<ct<<endl;
	}
	return 0;
}