We call one integer beautiful, if and only if it is divisible by each of its non-zero digits. Given an interval [l, r], calculate how many beautiful numbers n satisfy l<=n<=r.

Input

First line, the number of test cases, t.

Then t lines follow, each line two numbers l, r, representing the query interval [l, r].

1<=t<=2.5*10^4

1<=l<=r<=10^18

Output

t lines. The t-th line is the answer to the t-th query.

Example

Input:
1
1 100

Output:
33