C :

#include <stdio.h>
int main(){
    int s, i;
    scanf("%d", &s);
    while(s--){
        int t, m, n, cnt = 0;
        scanf("%d %d", &n, &m);
        for(i = 1; i <= n; i++){
            t = i;
            while(t%m == 0){
                cnt++;
                t /= m;
            }
        }
        printf("%d\n", cnt);
    }
    return 0;
}

C++ :

 #include<iostream>
 using namespace std;
 int main()
 {
     int k,i,j,n,m,w,a;
     cin>>k;
     while(k--)
     {
         w=a=0;
         cin>>n>>m;
         for(i=2;i<=n;i++)
         {
             j=i;
             while(j%m==0&&j)
             {
                 j=j/m;
                 a++;
             }
            w+=a;
             a=0;
         }
         cout<<w<<endl;
     }
     return 0;
 }