#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <set>

#define ll long long

using namespace std;

#define N 100007

int prime[] = {, , , , , , , , , , , , , , , , , , , };

int n,p;

set<ll> ans;

void dfs(int ind,int now,ll num)

{

    ans.insert(num);

    if(now < prime[ind])

        return;

    dfs(ind,now-prime[ind],num*prime[ind]%p);  //分解这个

    dfs(ind+,now,num);  //不分解这个

}

int main()

{

    int t;

    scanf("%d",&t);

    while(t--)

    {

        scanf("%d%d",&n,&p);

        ans.clear();

        dfs(,n,);

        printf("%d\n",ans.size());

    }

    return ;

}