Mike found an interesting problem. In this problem you are given two integers, n and k. You need to find the the maximum value of x, such that, n! % kx = 0.
Input Format
First line contains number of test cases, T. Each test case contains two integers each, n and k.
Constraints
1<=T<=20 1<=n<=10^8 2<=k<=10^8
Output Format
Print the value of x for each test case.
Sample Input
2
5 2
1000 2
Sample Output
3
994
Explanation
In the first test case, n = 5 and k = 2. So, n! = 120. n! % 2^0 = 0, n! % 2^1 = 0, n! % 2^2 = 0, n! % 2^3 = 0, n! % 2^4 = 8, n! % 2^5 = 24, n! % 2^6 = 56, n! % 2^7 = 120. So, the answer should be 3.
Code:
#include
#include
#include<bits/stdc++.h>
#define l long long int
using namespace std;
set primefactors(l n){
set s;
while(n%2 == 0){
s.insert(2);
n = n/2;
}
for(l i=3;i<=sqrt(n);i++){
while(n%i == 0){
s.insert(i);
n = n/i;
}
}
if(n > 2){
s.insert(n);
}
return s;
}
l power(l k,l x){
if(x == 0){
return 1;
}
if(x == 1){
return k;
}
l smallans = power(k,x/2);
if(x%2 == 0){
return (smallans*smallans);
}
return ((smallans*smallans)*k);
}
l answer(l n,l k){
l i = 1;
l mm = (n/power(k,i));
l ans = 0;
while( mm >= 1){
ans += mm;
i++;
mm= (n/power(k,i));
}
return ans;
}
int main(){
l t;
cin>>t;
while(t–){
l n,k;
cin>>n>>k;
set s = primefactors(k);
l ans = INT_MAX;
for(auto a: s){
l kk = answer(n,a);
if(kk < ans){
ans = kk;
}
}
cout<<ans<<endl;
}
return 0;
}