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.
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.
You should output Q lines, each of them containing the answer to a query.
- 1 ≤ Q ≤ 50 000
- 1 ≤ a ≤ b ≤ 50 000
For the second query, the special subintervals are:
Hint: Mo's Algorithm