Let f(x) be the product of digits of a number.

Given L and R, find the number of values of 'i' such that L ≤ i ≤ R and f(i) is even.

Input

The first line consists of an integer t, the number of test cases. For each test case, you are given the two integers L and R.

Output

For each test case, print the number of values of 'i' such that L ≤ i ≤ R and f(i) is even.

Constraints

1 ≤ t ≤ 100

1 ≤ L ≤ R ≤ 1000000000

Sample

Input:
2
2 12
4 23

Output:
6
12