KOPC12H - K12-OE Numbers


Rishi loves numbers and number patterns very much. He is interested in finding OE numbers in a range [a, b]. An OE number is a number whose sum of even digits [0, 2, 4, 6, 8] is greater than sum of odd digits [1, 3, 5, 7, 9]. Help him to count how many OE numbers are in range [a, b] {a and b inclusive}

Example: 
  - 4563: O = 5+3   = 8, E = 4+6 = 10, E > O, so 4563 is an OE number
  - 1233, O = 1+3+3 = 7, E = 2,        E < O, so 1233 is not an OE number
  -   10, O = 1,         E = 0         E < O, so 10 is not an OE number

Input

The first line of the input file contains T which denotes the number of Test cases. The next T lines contains two space separated integers a and b.

1 <= a <= b <=10^8
T <= 35.

Output

Print the number of OE numbers in range [a, b] {one number per line}

Example

Input:
3
1 1
2 10
1 100000000

Output:
0
4
38379932

hide comments
rangey_18o3_20: 2021-08-28 17:29:08

Great question for those new to digit dp

vikas_007: 2020-10-18 10:23:27

pretty basic digitDp question..

pratham_1: 2017-10-18 12:32:11

CakeWalk;)

the_phoenixx: 2017-07-02 07:59:39

Nice digitdp !!

Sigma Kappa: 2017-06-26 02:32:43

Excellent problem.

#vaidy_MIT#: 2012-04-06 18:00:11

@Ab007 ...frm kurukshetra..2012 ..conducted by anna university..

Abhishek Verma: 2012-02-05 15:25:49

good one...gt ac :)
from which contest is this problem from?

Last edit: 2012-02-05 16:57:21

Added by:Radhakrishnan Venkataramani
Date:2012-01-31
Time limit:0.100s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64