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
sajalhawk:
20180729 21:51:37
I am using Python 3 and the following method to initialise the list : dp = [[[[1 for l in range(60)]for k in range(60)] for j in range(60)] for i in range(51)]. But it is taking a long time to execute. Please suggest any alternative 

sxie12:
20180213 04:43:12
dp[51][18][18][18][2] TLE > dp[51][36][36][2][2] AC


siddiboy:
20170601 22:17:51
1 10^50


datbeohbbh:
20170522 06:22:56
finally AC,silly mistake 

kr1996:
20160623 22:49:15
1 > 10^50 : 129112454 

kejriwal:
20160124 18:38:34
Awesome Problem :') 

naruto09:
20160121 22:03:24
still cant figure out why i am getting WA..._ 

ashish kumar:
20160118 18:18:30
finally accepted 

Vu Duy Truc:
20151112 09:09:47
Please give me some testcase ???


elita lobo:
20150808 13:39:34
@Saransh Bansal, Can you please check my code and tell me why I am getting wa? id 14848296 
Added by:  Saransh Bansal 
Date:  20120321 
Time limit:  0.391s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 