NUMTSN - 369 Numbers

no tags 

7. 369 numbers

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

 


hide comments
freak2: 2020-11-20 07:46:41

even dp[51][17][17][2][2] giving tle

Last edit: 2020-11-20 07:47:18
dangtiendung: 2020-11-11 10:47:56

Hoàng Anh Minh - 11 Tin - Chuyên Thái Bình trâu cũng AC

Last edit: 2020-11-11 10:48:16
pranay_garg: 2019-10-10 14:50:51

How does it work if we initialize dp[] only once before test cases??

sahilshelangia: 2019-10-10 13:41:06

Last edit: 2019-10-10 13:41:31
zephyr_96: 2019-10-08 10:11:11

dp[51][55][55][55] gets TLE in java but AC in C++.

quanpham0805: 2019-06-01 18:55:44

nhật hào bẩn

Last edit: 2019-06-01 19:01:34
tranminhkhang7: 2019-05-22 10:47:50

Last edit: 2019-05-22 10:49:36
tototete: 2019-05-22 08:17:19

trâu cũng AC

zingme123aptx: 2019-05-20 10:55:18

trâu cũng AC

harshit2202: 2019-03-22 13:47:35

We should fill(dp,-1) in every test case. but this will give TLE.
How to avoid that.?
dp[50][2][17][17][17].


Added by:Saransh Bansal
Date:2012-03-21
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64