#include<iostream>
#include<cstring>
using namespace std;
int t, n, a, jc[10000], len;
int main(){
	cin >> t;
	while(t--){
		cin >> n >> a;
		memset(jc, 0, sizeof(jc));
		jc[1] = 1;
		int len = 1;
		for(int i = 2; i <= n; i++){
			for(int j = 1; j <= len; j++){
				jc[j] *= i;
				jc[j + 1] += jc[j] / 10;
				jc[j] %= 10;
			}			
			int temp = jc[len + 1];
			while(temp){
				jc[++len] = temp % 10;
				temp /= 10; 
			}
		}	
		int cnt = 0;
		for(int i = len; i >= 1; i--)		
			if(a == jc[i]) cnt++;		
		cout << cnt << endl;		
	}
	return 0;
}