Digit dp

/// Code is tested on https://www.hackerrank.com/contests/february-codeblast-2019/challenges/trouble-with-fake-id/problem 
#include <bits/stdc++.h>
#define ll long long
using namespace std;
vector<ll> num1,num2;
ll dp[20][20][2][2][2],a,b,d,k;
ll call(ll pos, ll cnt, ll f,ll st,ll sm,ll p,ll q)
{
    if(pos == num2.size())
    {
        if(cnt >= p&&cnt<=q&&st)
            return 1;
        return 0;
    }

    if(dp[pos][cnt][f][st][sm]!= -1)
        return dp[pos][cnt][f][st][sm];

    ll tem,res=0,nf,ncnt,nst,i,nsm;
    tem = f?9:num2[pos];
    i=sm?0:num1[pos];
    for(; i<=tem; i++)
    {
        nf = f;
        ncnt = cnt;
        nsm=sm;
        nst=st;
        if(i>0) nst=1;
        if(i<tem) nf = 1;
        if(i == d&&nst) ncnt++;
        if(i>num1[pos]) nsm=1;
        res += call(pos+1,ncnt,nf,nst,nsm,p,q);
    }
    return dp[pos][cnt][f][st][sm] = res;
}
ll solve(ll b,ll a,ll p,ll q)
{
    num1.clear();
    num2.clear();

    while(a>0)
    {
        num1.push_back(a%10);
        a/=10;
    }
    while(b>0)
    {
        num2.push_back(b%10);
        b/=10;
    }
    while(num1.size()<num2.size())
        num1.push_back(0);

    reverse(num1.begin(), num1.end());
    reverse(num2.begin(), num2.end());
    ll res=0;
    res += call(0, 0,0,0,0,p,q);
    return res;
}

int main ()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    ll t,l,r,i,res=0;
    scanf("%lld",&t);
    while(t--)
    {
        memset(dp,-1,sizeof(dp));
        res=0;
        scanf("%lld %lld %lld %lld %lld",&a,&b,&d,&l,&r);
        if(a==0&&d==0&&l<=1&&r>=1)
            res=1;
        else if(a==0&&d!=0&&l==0)
            res=1;
        res += solve(b,a,l,r);
        printf("%lld\n",res);
    }
    return 0;
}