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