Felix Halim .NET  
Google 

ACM/ICPC Indonesia National Contest 2007

Problem E

The Adventure in Panda Land Part I: Panda Number

Time Limit: 1s


In Panda Land, pandas have their own numeral system to represent a number. Surprisingly, this numeral system is similar to the famous Roman Numerals in our ancient civilization. Although pandas are aware about numeral system, they can not write (imagine how can a panda write!). Instead, they cut and arrange bamboos to form a number.

Decimal Panda Number Required Bamboo
1I1
5V2
10X2
50L2
100C3
500N3
1,000M4
5,000E4
10,000W4
50,000F3
100,000Y3
500,000K3
1,000,000H3
5,000,000T2
10,000,000A3
  These are the production rules of Panda Number:
  • Letters which represent powers-of-ten (I, X, C, M, W, Y, H, A) can be repeated at most three times. The others (V, L, N, E, F, K, T) can not be repeated.
  • If one or more letters are placed after another letter of greater value, add that amount. The letters should be written in descending order from the largest to the least value. For example:
    FXVIII = 50000 + 10 + 5 + 1 + 1 + 1 = 50018
  • If a letter is placed before another letter of greater value, subtract that amount. Only subtract one letter from another. For example:
    XIV = 10 + (5 - 1) = 14
    CIX = 100 + (10 - 1) = 109
    MECIX = (5000 - 1000) + 100 + (10 - 1) = 4109
  • Only powers-of-ten can be used to subtract a value (that is, you can subtract I from V, or X from L, but not V from X (V is not powers-of-ten.)
  • Do not subtract a letter from one that is more than 10 times greater (that is, you can subtract I from X, but not I from L there is no such number as IL.)

The aforementioned rules imply that there is exactly one representation in Panda Number for each number in decimal system.

Unlike those Roman Numerals, pandas do recognize zero and negative number (which prove pandas are more advanced than our ancient Romans). To represent a negative number, they add one bamboo as a negative sign in front of the letters. Zero is a special number which doesn't fall into any rules above. To form a zero, pandas need five bamboos.

The number of bamboos needed to form a number is the sum of required bamboos for each letter that appears in that number. For Example:
4108 = 4000+100+8 = (5000-1000)+100+5+1+1+1 = MECVIII (16 bamboos).
4109 = 4000+100+9 = (5000-1000)+100+(10-1) = MECIX (14 bamboos).
-205 = [-], 200+5 = 100+100+ 5 = -CCV (9 bamboos)

Given two numbers A and B, find out how many bamboos needed by panda to form (remember, they can't write) all number between A and B inclusively.

Input

The input begins with a single positive integer T in a line indicating the number of test cases. Each case contains two numbers A and B (-25,000,000 <= A <= B <= 25,000,000) in a line.

Output

For each case, print in a single line the number of needed bamboos to form all numbers between A and B (inclusive).

Sample Input

7
-1 1
4018 4019
-25000000 25000000
-100 -57
-100 0
0 100
43 100

Sample Output

8
28
2121000021
399
778
678
434


Problem Setter: Evan Leonardi


Kembali ke pembahasan soal ini

Lihat problem lain:

  1. Minimum Swap
  2. GCD!
  3. Playing With Domino
  4. Email from the Professor
  5. Panda Number
  6. Jakarta Traffic Jam
  7. Sultan's Land
  8. Tree Median


© Felix Halim 2009 (Loaded in 0.00160 secs)