RAONE - Ra-One Numbers

In the War between good and evil . Ra-One is on the evil side and G-One on the good side.

Ra-One is fond of destroying cities and its G-one's duty to protect them..

 

Ra-One loves to destroy cities whose Zip Code has special properties. He says he loves to destroy cities which have Ra-One numbers as their Zip Code.

Any number is Ra-one if the Difference between Sum of digits at even location and Sum of digits at odd location is One (1).. For eg... for 234563 is Ra-One number

digits at odd location are 3,5,3 (unit place is location 1 )

digits at even location are 2,4,6

Diff = (2+4+6)-(3+5+3)=12-11 = 1.

And 123456 is not Ra-One number

diff = (5+3+1) - (2+4+6) = -4

 

G-One knows this about Ra-one and wants to deploy his Army members in those cities. 1 army member will be deployed in each city.

G-one knows the range of ZIP-Codes where Ra-One might attack & needs your help to find out how many army members he needs.

Can you help Him ?

Input

First line will have only one integer 't' number of Zip-Code ranges. it is followed by t lines

Each line from 2nd line contains 2 integer 'from'  and 'to'. These indicate the range of Zip codes where Ra-one might attack. ('From' and 'to' are included in the range)

NOTE:'t' will be less than 100. 'from' and 'to' will be between 0 and 10^8 inclusive.

Output

A single number for each test case telling how many army members G-One needs to deploy.

each number should be on separate lines

Example

Input:
2
1 10
10 100

Output:
1
9

explanation:

for 1st test case the only number is 10

for 2nd test case numbers are 10, 21, 32, 43, 54, 65, 76, 87, 98


Added by:Devil D
Date:2012-02-21
Time limit:0.101s
Source limit:30000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own

hide comments
2017-10-18 12:07:54
YEAHHH!!!!! I solved it in java , I deserve some prize;) Strict time limit... spent almost 3-4weeks;)
2017-09-09 07:34:04
@sucide i used the same approach dp[index][esum-osum][fix] but getting timeout;(
2017-06-12 02:53:40
ac in one go ,,, just keep it simple (dp[idx][sume-sumo][fix])
2016-02-01 14:56:27 Liquid_Science
Fastest solution in JAVA atleast , though it can be optimized further :P
2015-01-17 10:10:37 KAI
1st attempt ac :)
2014-12-30 23:21:13 thecodekaiser
@Devil D: Please check why I am getting WA..my code is giving right ans for above test cases and also for cases given in the comments
2014-09-30 12:14:14 Gaurav Kumar Verma
despite of lot of attempts i am got TLE eveytime.
Any hint please??
2013-07-02 06:34:37 SWOOSH!!!
Thanks a lot Mitch I get it now.
2013-07-01 22:22:24 Mitch Schwartz
The units place is the least significant digit. It seems you are looking at it backwards.
2013-07-01 14:36:04 SWOOSH!!!
@Mitch thanks for the clarification, but my other doubt is still not clear, that 100 and 10 will both result in -1 according to question.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.