SUMSLOPE - Summing Slopes

no tags 

A digit in a number N is a minima if it is lesser than both the digits adjacent to it. Similarly, a digit is a maxima if it is greater than both the digits adjacent to it. The slope of N is the number of digits in N (leaving out the first and the last digit) which are either a minima or a maxima. Given A and B, count the sum of the slopes of all numbers between A and B.

Input

The first line contains the number of test cases T. Each of the next T lines contains two integers A and B.

Output

Output T lines one for each test case, containing the required sum for the corresponding test case.

Sample

Input
3
101 101
1 100
100 150

Output
1
0
19

Constraints

1 <= T <= 50000

1 <= A <= B <= 1000000000000000 (10^15)


hide comments
[Rampage] Blue.Mary: 2017-08-30 06:50:39

With updated compiler C++14, O(digit * base) per test case can easily get AC.

In my opinion, it's pointless to reject O(digit*base) solution. If it's desired, the problem setter should set limit to: length = 1000, base = 1000, nTest = 1000 and time limit = 1 - 2 seconds.

Last edit: 2017-08-30 06:57:08
heathens: 2016-12-27 15:15:28

varun can you pm me how to do digits+base ? im doing it digits*base

Ivan Katanic: 2010-09-28 07:08:41

well mine is O( digits + base ) per test case too, but usually we should make time limit at least 0.5 s more authors solution runs.

Varun Jalan: 2010-09-28 07:08:41

Increased time limit to 2 seconds.

Varun Jalan: 2010-09-28 07:08:41

@ Ivan : My solution takes 0.8 seconds without speed IO. I have O(digits + base) per test case (not O(digits * base)).

Last edit: 2010-07-27 07:42:02
gustav: 2010-09-28 07:08:41

You should seriously consider making the time limit less strict, 1s is ridiculous. Also, as Oleg said, the actual limit on A and B is not 10^9 but 10^15.

Last edit: 2010-07-26 21:12:43
Ivan Katanic: 2010-09-28 07:08:41

I think that time limit is too strict, how fast is your solution and do you have any dirty optimizations?


Added by:Varun Jalan
Date:2010-07-26
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS OBJC PERL6 VB.NET
Resource:own problem