D. Double Pleasure
time limit per test
3 с
memory limit per test
256 megabytes
input
standard input
output
standard output

Hsueh- especially likes pleasure number because these numbers make people feel happy.

A number is a pleasure number, iff it is an integer, and the greatest common factor of the product of its digits and the number itself is not $$$1$$$.

It is worth noting that:

  • The greatest common factor of $$$0$$$ and $$$x$$$ ($$$x \gt 0$$$) is $$$x$$$.
  • $$$0$$$ and $$$0$$$ have no greatest common factor.

For instance：

  • $$$33$$$ is the pleasure number, because $$$3 \times 3 = 9$$$, the greatest common factor of $$$9$$$ and $$$33$$$ is $$$3$$$.
  • $$$233$$$ is not a pleasure number because $$$2 \times 3 \times 3 = 18$$$, and the greatest common factor of $$$18$$$ and $$$233$$$ is $$$1$$$.

Hsueh- wants to know how many pleasure numbers in the range $$$[A, B]$$$.

Input

The first line contains a single integer $$$T(1 \leq T \leq 10^4)$$$, denoting the number of test case.

For next $$$T$$$ lines, each line contains two integer $$$A, B(1 \leq A, B \leq 10^{18})$$$, representing the range $$$[A, B]$$$.

Output

For each test case, print a single integer, denoting the answer.

Example
Input
2
1 2
3 4
Output
1
2