Akarshita has a thing for even numbers but when it comes to odd numbers, she hates them. She loves even numbers because she considers them lucky as she was born in an even year. She is so much in love with them that she has even number of houses, she wears even number of watches, her car number is even and whenever she goes to cinema halls, her seat number is even always.
Mohini, her friend, seeing Akarshita so obsessed with even numbers has brought a problem for her. Mohini provides Akarshita with a lower (L) and an upper (U) limit. She then asks Akarshita to tell her the total count of numbers in the given range (both included), the summation of whose subsequences comes out to be an even number.
A subsequence is a sequence that can be derived from another sequence by deleting zero or more elements without changing the order of the remaining elements.
Example:
N = 123.
The subsequences for N are {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}
Akarshita has no clue about such numbers and has asked Mohini for an example.
Example:
N = 241
Subsequences = {2}, {4}, {1}, {2, 4}, {2, 1}, {4, 1}, {2, 4, 1}
Summation of Subsequences = {2} + {4} + {1} + {24} + {21} + {41} + {241} = 334
Akarshita is not able to find the correct numbers for the given range by Mohini. Can you help her find the total such numbers in the range provided by Mohini?
Input Format
The first line of input consists of the number of test cases, T
The only line of each test case consists of two space-separated integers, L and R.
Constraints
1<= T <=10
1<= L <= R <=10^10 (1e10)
Output Format
For each test case, print the required output in a separate line.
Sample TestCase 1
Input
2
1 10
22 25
Output
4
4
Explanation
Test Case 1:
The given range is [1, 10]. There are 4 numbers in this range with the sum of their subsequences as even.
Numbers 2, 4, 6 and 8 are the numbers with the sum of their subsequences as even.
Test Case 2:
The given range is [22, 25].
N = 22
Subsequences = {2}, {2}, {2, 2}
Sum of Subsequences = {2} + {2} + {22} = 26
N = 23
Subsequences = {2}, {3}, {2, 3}
Sum of Subsequences = {2} + {3} + {23} = 28
N = 24
Subsequences = {2}, {4}, {2, 4}
Sum of Subsequences = {2} + {4} + {24} = 30
N = 25
Subsequences = {2}, {5}, {2, 5}
Sum of Subsequences = {2} + {5} + {25} = 32
There are 4 numbers in the given range with the sum of their subsequences as even.
