#include <cstdio>
#include <set>
using namespace std;

set<long long> s[71];

void init(){
	s[1].insert(1);
	for(int i=2;i<=70;++i){
		s[i].insert(i);
		for(int j=1;j<i;++j){
			for(set<long long>::iterator it=s[i-j].begin();it!=s[i-j].end();++it){
				s[i].insert(*it*j);
			}
		}
	}
	
/*	for(int i=1;i<=70;++i){
		printf("sz=%d ", s[i].size());
		for(set<long long>::iterator j=s[i].begin(); j!=s[i].end(); ++j){
			printf("%lld ", *j);
		}
		puts("");
	}
*/
}

set<long long> v;

int main(){
	init();
	int T;
	scanf("%d", &T);
	while(T--){
		v.clear();
		int n, p;
		scanf("%d%d", &n, &p);
		for(set<long long>::iterator it=s[n].begin(); it!=s[n].end(); ++it){
			v.insert((*it) % p);
		}
		printf("%d\n", v.size());
	}
}
