#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<ctype.h>
#define S 40005
using namespace std;
inline void rd(int &res){
    char c;res=0;
    while(c=getchar(),c<48);
    do res=res*10+(c&15);
    while(c=getchar(),c>47);
}
int T,n,m,s,prime[S];
bool mark[S];
void Int(){
    for(int i=2;i<S;++i)
        if(!mark[i]){
            prime[++s]=i;
            for(int j=i;j<S;j+=i)mark[j]=1;
        }
}
int solve(int n,int d){
    int k=n/d;
    if(k<=1)return 0;
    int s=min(k,d);
    int cnt=0;
    for(int i=1;prime[i]<=s;i++){
        if(d*prime[i]!=n){
            cnt++;
        }
        if(d%prime[i]==0)break;
    }
    return cnt;
}
int main(){
    rd(T);Int();
    while(T--){
        rd(n);rd(m);
        printf("%d\n",solve(n,m));
    }
    return 0;
}