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⁴

1 ≤ l ≤ r ≤ 10¹⁸

Output

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

Example

Input:
1
1 100
Output:
33