#include<iostream>
#include<math.h>
using namespace std;
int i,j,v[100],b,a[100][100],nr,f,g,h;
double x,y,c,n;
int main(){
    cin>>h;
    for(i=1;i<=h;i++)
        for(j=1;j<=2;j++)
        cin>>a[i][j];
    for(i=1;i<=10;i++){
            f=0;
            nr=0;
        for(j=1;j<=a[i][1];j++){
            for(b=1;b<=j;b++)
               x=x*b;
        y=y*x;
        }
        while(y!=0){
            c=fmod(y,a[i][2]);
            y=n/a[i][2];
            v[++f]=c;
        }
    for(g=f;g>=1;g--)
        if(v[g]==0)
           nr++;
           else break;
     cout<<nr<<endl;
    }
    return 0;}