Interesting Strobogrammatic Numbers

A number is called interesting if, when it is written on an opaque piece of paper using a special font and the paper is rotated by 180° (with the rotation axis perpendicular to the paper), it appears as the same number. In other words, if the digit sequence of the number is S = s₁s₂...s_n, and each digit transforms according to the mapping

$$0\to0,\quad 1\to1,\quad 6\to9,\quad 8\to8,\quad 9\to6, $$

then after rotation the number becomes

$$f(s_{n})\;f(s_{n-1})\;...\;f(s_{1}),$$

and it must satisfy $$s_i = f(s_{n-i+1})\quad \text{for }\, i=1,2,...,n. $$

For example, 69 is interesting because rotating the paper swaps the digits and transforms them: the 6 becomes a 9 and the 9 becomes a 6, so the resulting image still reads 69.

You are given Q queries. Each query consists of two integers L and R, and you have to count how many interesting numbers lie in the inclusive range [L, R].

## inputFormat

The first line contains a single integer Q, the number of queries.

Each of the next Q lines contains two integers L and R separated by a space.

Note: It is guaranteed that the input numbers are non-negative and do not contain extra leading zeros.

## outputFormat

For each query, output a single line containing the count of interesting numbers in the range [L, R].

## sample

1
0 100

7

$$