#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N=,M=1e4+;

int t,k,n[M],m[M],mxn,mxm,mx,a[N][],dp[N][N],cnt,zs[],nm[];

int rdn()

{

    int ret=;char ch=getchar();

    while(ch>''||ch<'') ch=getchar();

    while(ch>=''&&ch<='') ret=(ret<<)+(ret<<)+ch-'',ch=getchar();

    return ret;

}

int main()

{

    t=rdn();k=rdn();

    for(int i=;i<=t;i++)

        n[i]=rdn(),m[i]=rdn(),mxn=max(mxn,n[i]),mxm=max(mxm,m[i]);

    mx=max(mxn,mxm);

    int tmp=k;

    for(int i=;i<=tmp;i++)

        if(tmp%i==)

        {

            zs[++cnt]=i;

            while(tmp%i==)tmp/=i,nm[cnt]++;

        }

    for(int i=;i<=mx;i++)

        for(int j=,s=i;j<=cnt;j++,s=i)

            while(s) s/=zs[j],a[i][j]+=s;//数i含有多少第j个质因数

//    for(int i=1;i<=mx;i++) printf("a[%d]=%d\n",i,a[i]);

    for(int i=;i<=mxn;i++)

    {

        for(int j=;j<=mxm&&j<i;j++)

        {

            dp[i][j]=dp[i][j-]+dp[i-][j]-dp[i-][j-];

            bool flag=;

            for(int o=,d;o<=cnt;o++)

            {

                d=a[i][o]-a[j][o]-a[i-j][o];

                if(d<nm[o]){flag=;break;}

            }

            dp[i][j]+=(!flag);

//            printf("dp[%d][%d]=%d(ai-aj-a(i-j)=%d)\n",i,j,dp[i][j],

//                a[i]-a[j]-a[i-j]);

        }

        for(int j=i;j<=mxm;j++) dp[i][j]=dp[i][j-];

//            printf("dp[%d][%d]=%d\n",i,j,dp[i][j]);

    }

    for(int i=;i<=t;i++)

        printf("%d\n",dp[n[i]][m[i]]);

    return ;

}