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
| Input | Output | Explanation | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 3 1 3 1 7 4 7 | 6 13 4 | For the second query, the special subintervals are:
|
Hint: Mo's Algorithm
