# Count 47

An interval is called special if, by concatenating the string representation of all integers it contains, we have that digit 4 has the same number of occurrences (possibly none) as digit 7. For instance, [8, 28] is a special interval, because 4 and 7 both appear twice in "8910111213141516171819202122232425262728".

You are given Q queries of the form [a, b]. For each query, you need to compute how many sub-intervals [x, y] (a ≤ x ≤ y ≤ b) are special.

### Input

The first line of input contains an integer Q.
Each of the following Q lines contains two space-separated integers a b.

Note: if you use C++ I/O streams, please add cin.sync_with_stdio(false); before reading the input, in order to improve I/O speed.

### Output

You should output Q lines, each of them containing the answer to a query.

### Constraints

• 1 ≤ Q ≤ 50 000
• 1 ≤ a ≤ b ≤ 50 000

### Sample

InputOutputExplanation
3
1 3
1 7
4 7
6
13
4

For the second query, the special subintervals are:

IntervalConcatenationFrequency of 4Frequency of 7
[1, 1]100
[1, 2]1200
[1, 3]12300
[1, 7]123456711
[2, 2]200
[2, 3]2300
[2, 7]23456711
[3, 3]300
[3, 7]3456711
[4, 7]456711
[5, 5]500
[5, 6]5600
[6, 6]600
Questions?