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 subintervals [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 spaceseparated 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