NUMTSN  369 Numbers
7. 369 numbers
A number is said to be a 369 number if
 The count of 3s is equal to count of 6s and the count of 6s is equal to count of 9s.
 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
hide comments
pranay_garg:
20191010 14:50:51
How does it work if we initialize dp[] only once before test cases??


sahilshelangia:
20191010 13:41:06
Last edit: 20191010 13:41:31 

zephyr_96:
20191008 10:11:11
dp[51][55][55][55] gets TLE in java but AC in C++. 

quanpham0805:
20190601 18:55:44
nhật hào bẩn


tranminhkhang7:
20190522 10:47:50
Last edit: 20190522 10:49:36 

tototete:
20190522 08:17:19
trâu cũng AC 

zingme123aptx:
20190520 10:55:18
trâu cũng AC 

harshit2202:
20190322 13:47:35
We should fill(dp,1) in every test case. but this will give TLE.


iceelement:
20190125 07:09:23
It will TLE if you keep counts of all numbers, or even if you keep counts/3, keep [cnt6cnt3] and [cnt9cnt6], also optimize based on the fact that the difference can't be outside [17,+17]. TLE's if you do the [0,r]  [0,l1] type of digit dp which uses single flag, use [l,r] type dp which uses 2 flags instead. AC in 0.37 seconds in CPP14 after these optimizations. 

bruzelee:
20181217 02:16:08
iam getting WA, donno why Last edit: 20181217 02:29:56 
Added by:  Saransh Bansal 
Date:  20120321 
Time limit:  0.391s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 