369.cpp

// coder : adist98
// Given two long long integers a and b. The task is to prlong long int
// sum of all the digits appearing in the
// long long integers between a and b
#include "bits/stdc++.h"
using namespace std;

// Memoization for the state results
long long int dp[52][50][50][50][2];

// Stores the digits in x in a vector digit
long long getDigits(long long x, vector <long long int> &digit)
{
	while (x)
	{
		digit.push_back(x%10);
		x /= 10;
	}
}

// Return sum of digits from 1 to long long integer in
// digit vector
long long digitSum(long long int idx, long long int sum3, long long int sum6, long long int sum9, long long int tight,
						vector <long long int> &digit)
{
	// base case
	if (idx == -1){
        if((sum3 == sum6) && (sum6 == sum9) && (sum3 >= 1)){
            return 1;
        }else{
            return 0;
        }
	}

	// checking if already calculated this state
	if (dp[idx][sum3][sum6][sum9][tight] != -1 && tight != 1)
		return dp[idx][sum3][sum6][sum9][tight];

	long long ret = 0;

	// calculating range value
	long long int k = (tight)? digit[idx] : 9;

	for (long long int i = 0; i <= k ; i++)
	{
		// caclulating newTight value for next state
		long long int newTight = (digit[idx] == i)? tight : 0;
        if(i == 3){
            ret += digitSum(idx-1, sum3+1, sum6, sum9, newTight, digit);
        }else if(i == 6){
            ret += digitSum(idx-1, sum3, sum6+1, sum9, newTight, digit);
        }else if(i == 9){
            ret += digitSum(idx-1, sum3, sum6, sum9+1, newTight, digit);
        }else{
            ret += digitSum(idx-1, sum3, sum6, sum9, newTight, digit);
        }

	}

	if (!tight)
	dp[idx][sum3][sum6][sum9][tight] = ret;

	return ret;
}

// Returns sum of digits in numbers from a to b.
long long int rangeDigitSum(long long int a, long long int b)
{
	// initializing dp with -1
	memset(dp, -1, sizeof(dp));

	// storing digits of a-1 in digit vector
	vector<long long int> digitA;
	getDigits(a-1, digitA);

	// Finding sum of digits from 1 to "a-1" which is passed
	// as digitA.
	long long ans1 = digitSum(digitA.size()-1, 0,0,0, 1, digitA);

	// Storing digits of b in digit vector
	vector<long long int> digitB;
	getDigits(b, digitB);

	// Finding sum of digits from 1 to "b" which is passed
	// as digitB.
	long long ans2 = digitSum(digitB.size()-1, 0,0,0, 1, digitB);

	return (ans2 - ans1);
}

// driver function to call above function
int main()
{
	int t;
	cin >> t;
	while(t--){
        double a,b;
        cin >> a >> b;
        cout << rangeDigitSum((long long int)a,(long long int)b) << endl;
	}
	return 0;

}