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
2012-03-16 04:55:20 Devil D
@surya - Your output is wrong for more then 50% test cases.. Check for overflow conditions ...
2012-03-16 04:55:20 Surya kiran
p.s please check my code i am getting WA..but for sample I/O its correct and some other cases also i tested

Last edit: 2012-02-24 14:53:07
2012-03-16 04:55:20 Devil D
@gaurav - Ur answer are correct only for examples..
for 100 110 the answer is 0
you are getting 1
@marcos - there are a small fault in test case .. changed and rejudged .. Your solution got AC

Last edit: 2012-02-22 10:47:24
2012-03-16 04:55:20 Marcos Kawakami
are there any tricky cases? I've been testing my solution with a bruteforce algorithm using random inputs and the outputs seem to be matching.

Last edit: 2012-02-21 19:25:27
2012-03-16 04:55:20 Gaurav
got my mistake...

Last edit: 2012-02-22 09:10:29
2012-03-16 04:55:20 Devil D
@gaurav .... Ur answer is correct only for examples given above ....

Last edit: 2012-03-02 03:57:28
2012-03-16 04:55:20 Gaurav
can you pls chk my code....i dnt knw why im getting WA....
2012-03-16 04:55:20 Devil D
@Fendy
1 and 100 are not ra-one numbers ..
here diff is -1 not 1

Last edit: 2012-03-05 05:57:38
2012-03-16 04:55:20 [Retired] Fendy Kosnatha
for second test case, why the answer is 9? not 11? coz i think ra-one number is 1 10 21 32 43 54 65 76 87 98 100...

Last edit: 2012-02-21 14:39:01
2012-03-16 04:55:20 Devil D
Also try
http://www.spoj.pl/problems/APGPS1/
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.