E. Nice (Medium Version)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

A number is nice if it contains only the digits $$$6$$$ and $$$9$$$. For example, $$$6$$$, $$$99$$$ and $$$69$$$ are nice numbers but $$$5$$$, $$$63$$$ and $$$169$$$ are not.

You are given two integers $$$l$$$ and $$$r$$$. Find the number of integers $$$m$$$, such that $$$l \leq m \le r$$$ and $$$m$$$ is nice.

Input

The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^{5}$$$) — the number of test cases.

The first and only line of each test case contains two integers $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le 10^{18}$$$).

Output

For each test case, print the number of nice numbers between $$$l$$$ and $$$r$$$.

Example
Input
4
1 10
66 99
69 6969
123123123123123 123123123123123
Output
2
4
17
0
Note

In the first test case, the nice numbers from $$$1$$$ to $$$10$$$ are $$$6$$$ and $$$9$$$, so the answer is $$$2$$$.

In the second test case, there are $$$4$$$ nice numbers from $$$66$$$ to $$$99$$$ and they are $$$66, 69, 96$$$ and $$$99$$$.