#include <cstdio>
#include <cstring>
#include <cassert>
using namespace std;
typedef unsigned long long LL;
#define FOR(k,a,b) for(int k((int)a); k < ((int)b); ++k)
#define REP(k,a) for(int k=0; k < ((int)a); ++k)

int T,MOD, F[10], FCount;
LL N;

int step(int addValue)
{
	if(F[addValue]==-1)
	{
		if(FCount == 0)
			return 1;
		if(FCount == 1)
			return 0;
		return FCount;
	}
	return F[addValue];
};

LL calc(int prMask, int len, int actRem)
{
	//this function calculate for some P prefix 
	//\sum_{i=0,i<10^len} F(P concenate i)%MOD
	//(actually we don't need P, just prMask because it is contains F(P) mask 
	// which numbers are reserved, and actRem = F(P)%MOD
	//this function is the soul of the solution this cause we don't need to 
	// calculate every F(i)%MOD
	actRem%=MOD;
	if(len == 0) return actRem;
	--len;
	if(!prMask)
	{
		return 9*calc(2,len,1);
	}
	if(prMask == 2)
	{
		return 9*calc(3,len,actRem*10)+calc(2,len,actRem*10+1);
	}
	LL res = 0;
	REP(i,10)
	{
		if(prMask&(1<<i))
		{
			res += calc(prMask,len,actRem*10+i);
		}
		else
		{
			res += (10-i)*calc(prMask|(1<<i), len, actRem*10+i);
			return res;
		}
	}
	return res;
}

int main( int argc, char* argv[] ) {
	scanf("%d",&T);
	while(T--)
	{
		scanf("%lld %d", &N, &MOD);
		memset(F, -1, sizeof F);
		FCount = 0;
		++N;
		LL res = 0, act = 0, tp = 1, pr = 1, addValue;
		int len = 0, prefixF = 0, prefixFMask = 0;
		while(tp*10<N)
		{
			tp*=10;
			++len;
		}
		FOR(i,1,len+1)
			res += calc(0,i,0);
		while(len>-1)
		{
			while((pr+1)*tp<=N)
			{
				addValue = step(pr%10);
				++pr;
				res += calc(prefixFMask|(1<<addValue),len,prefixF+addValue);
			}
			addValue = step(pr%10);
			prefixFMask|=(1<<addValue);
			prefixF=((prefixF+addValue)*10)%MOD;
			if(F[pr%10]==-1)
			{
				F[pr%10]=addValue;
				++FCount;
			}
			pr*=10;
			--len;
			tp/=10;
		}
		printf("%lld\n",res);
	}
	return 0;
}