digitDp.cpp

#include<bits/stdc++.h>
using namespace std;
#define ll long long


int dp[20][2][20][20];
int findClassyNumbers(string s, int curr, int flg, int cnt, int digits){
	if(curr==s.length()){
        return digits > 0 && digits <= 3 ? 1 : 0;
	}
	if(digits>3){
		return 0;
	}
	int limit = flg==1 ? s[curr]-'0' : 9;
	int ans=0;
	if(dp[curr][flg][cnt][digits]!=-1){
		return dp[curr][flg][cnt][digits];
	}
	for(int i=0;i<=limit;i++){
		int updatedDigits = digits;
		if(i>0){
			updatedDigits = digits + 1;
		}
		int updatedCnt = digits < 4 ? cnt+1 : 0;
		int updatedFlg = (i == limit) ? flg : 0;
		ans = ans + findClassyNumbers(s,curr+1,updatedFlg,updatedCnt,updatedDigits);
	}
	return dp[curr][flg][cnt][digits]=ans;
}



int main(){
	int x;
	cin>>x;
	while(x--){
		long long int l,r;
		cin>>l>>r;
    	memset(dp, -1, sizeof(dp));
		string right= to_string(r);
		int rightans = findClassyNumbers(right,0,1,0,0);
    	memset(dp, -1, sizeof(dp));
		string left= to_string(l-1);
		int leftans = findClassyNumbers(left,0,1,0,0);
		cout<<rightans-leftans<<endl;
	}
	return 0;
}