Find out how many numbers between a and b (inclusive) when represented as binary numbers have sum of digits lucky.

A number is lucky if its decimal representation contains digits 4 and 7 only.

eg. 4, 7, 47, 77 etc. where as 14, 41 etc. are not.

Note that 0 <= a <= b <= 10^19.

Input

T: number of test cases T<=10^5

Next T lines have a and b in every line. a <= b

Output

for every test case output as described in problem statement

Example

Input:
2
15 15
63 63
Output:
1
0