#include<bits/stdc++.h>
using namespace std;//万能头文件
#define int long long
const int N = 3005 ;  //定义c数组大小
int c[N] , a , n , t ;//定义 a ，n ，t
signed main(){
	cin >> t ;  //输入数据数
	while ( t-- ){
		int cnt = 0 ;   //个数和
		cin >> n >> a ; //输入每组数据
		memset( c , 0 , sizeof( c ) ) ; //c数组赋0
		c[1] = 1 ; 
		for ( int i = 2 ; i <= n ; i++ ){
			for ( int j = 1 ; j < N ; j++ )	c[j] *= i ; //小学乘法qwq
			for ( int j = 1 ; j < N ; j++ ){
				if ( c[j] >= 10 ){
					c[j+1] += c[j] / 10 ;  
					c[j] %= 10 ;  //小学学的满十进一qwq
				}
			}
		}    //重点高精度部分！！！
		int p = N - 1 ;  
		while ( c[p] == 0 && p > 0 ) p-- ; //消除前导0
		if ( p == 0 ){
			cout << 0 ;
			continue ; //如果木有，直接输出0
		}     
		for ( int j = p ; j >= 1 ; j-- ){
			if ( c[j] == a )	cnt++ ; //判断是否等于a
		}
		cout << cnt << endl ; //输出次数并换行
	}
	return 0;	//好习惯的养成
} 

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 3005 ;
int c[N] , a , n , t ;
signed main(){
	cin >> t ;
	while ( t-- ){
		int cnt = 0 ;
		cin >> n >> a ;
		memset( c , 0 , sizeof( c ) ) ;
		c[1] = 1 ;
		for ( int i = 2 ; i <= n ; i++ ){
			for ( int j = 1 ; j < N ; j++ )	c[j] *= i ;
			for ( int j = 1 ; j < N ; j++ ){
				if ( c[j] >= 10 ){
					c[j+1] += c[j] / 10 ;
					c[j] %= 10 ;
				}
			}
		}
		int p = N - 1 ;
		while ( c[p] == 0 && p > 0 ) p-- ;
		if ( p == 0 ){
			cout << 0 ;
			continue ;
		}
		for ( int j = p ; j >= 1 ; j-- ){
			if ( c[j] == a )	cnt++ ;
		}
		cout << cnt << endl ;
	}
	return 0;	
}