An integer $$n$$ is called a good number if it meets at least one of the following two conditions:

• $$n$$ is divisible by 7

• the digit 7 occurs in $$n$$

Determine how many good numbers occur in a given interval.

Input

The input consists of $$t$$ test cases ($$t \leq 200$$). The first line of the input contains an integer $$t$$. Then the description of the $$t$$ test cases follows. Each description of a test case contains one single line that contains the integers $$a$$ and $$b$$ ($$0 \leq a < b \leq 100.000$$), separated by one single space.

Output

For each test case, determine how many good numbers $$n$$ exist where $$a \leq n \leq b$$.

Example

Input:

5
12 930
9239 81736
7837 90943
636 33771
0 100000

Output:

349
37189
41901
14349
49386