## NUMTSN - 369 Numbers

no tags

A number is said to be a 369 number if

1. The count of 3s is equal to count of 6s and the count of 6s is equal to count of 9s.
2. The count of 3s is at least 1.

For Example 12369, 383676989, 396 all are 369 numbers whereas 213, 342143, 111 are not.

Given A and B find how many 369 numbers are there in the interval [A, B]. Print the answer modulo 1000000007.

Input

The first line contains the number of test cases (T) followed by T lines each containing 2 integers A and B.

Output

For each test case output the number of 369 numbers between A and B inclusive.

Constraints

T<=100

1<=A<=B<=10^50

Sample Input

3

121 4325

432 4356

4234 4325667

Sample Output

60

58

207159

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

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

#define MOD                 1000000007LL
#define EPS                 1e-9
#define io                  ios_base::sync_with_stdio(false);cin.tie(NULL);

const int MAXN = 1e5+5;

string a, b;
int n;
ll dp[55][55][55][55][2];

ll solve(string &s, int index, int count3, int count6, int count9, int isPrefixEqual){
if(dp[index][count3][count6][count9][isPrefixEqual] != -1)
return dp[index][count3][count6][count9][isPrefixEqual];
ll res = 0;
if(index == n){
if(count3 >= 1 && count3 == count6 && count6 == count9){
// cout << index << " " << count3 << " " << count6 << " " << count9 << " " << isPrefixEqual << endl;
// cout << count3 << " " << count6 << " " << count9 << endl;
return 1LL;
}
}else{
if(isPrefixEqual){
for(int i = 0; i <= s[index]-'0'; i++){
if(s[index]-'0' == i){
res += solve(s, index + 1, (i == 3) ? count3 + 1 : count3, (i == 6) ? count6 + 1 : count6, (i == 9) ? count9 + 1 : count9, 1);
res %= MOD;
}else{
res += solve(s, index + 1, (i == 3) ? count3 + 1 : count3, (i == 6) ? count6 + 1 : count6, (i == 9) ? count9 + 1 : count9, 0);
res %= MOD;
}
}
}else{
for(int i = 0;i <= 9; i++){
res += solve(s, index + 1, (i == 3) ? count3 + 1 : count3, (i == 6) ? count6 + 1 : count6, (i == 9) ? count9 + 1 : count9, 0);
res %= MOD;
}
}
}
dp[index][count3][count6][count9][isPrefixEqual] = res;
return res;
}

ll f(string &s){
int count3 = 0, count6 = 0, count9 = 0;
for(auto c : s){
if(c == '3')		count3++;
else if(c == '6')	count6++;
else if(c == '9')	count9++;
}
return (count3 >= 1 && count3 == count6 && count6 == count9);
}

int main(){
io;
int t;
cin >> t;
while(t--){
cin >> a >> b;
memset(dp, -1, sizeof dp);
n = b.size();
ll ansR = solve(b,  0, 0, 0, 0, 1);
memset(dp, -1, sizeof dp);
n = a.size();
ll ansL = solve(a, 0, 0, 0, 0, 1);
ll ans = (ansR - ansL + f(a)) % MOD;
ans = (ans + MOD) % MOD;
cout << ans << endl;
}
return 0;
}``````
Copy The Code &

Input

cmd
3
121 4325
432 4356
4234 4325667

Output

cmd
60
58
207159