판다 나라의 모험 1부: 판다 수

시간 제한1초메모리 제한128 MB

요약

음수와 0을 포함해 A부터 B까지 모든 정수를 팬더 숫자로 적을 때 필요한 대나무 개수의 합을 구한다.

문제

판다 나라의 판다들은 수를 나타내기 위한 고유한 기수법을 가지고 있는데, 놀랍게도 그 방식은 우리 고대 문명의 로마 숫자와 매우 비슷하다. 판다는 글씨를 쓸 수 없으므로(판다가 펜을 쥔 모습을 상상해 보라!) 대신 대나무를 잘라 늘어놓아 수를 만든다.

판다 수를 만드는 규칙은 다음과 같다.

10의 거듭제곱을 나타내는 글자(I, X, C, M, W, Y, H, A)는 최대 세 번까지 반복할 수 있다. 나머지 글자(V, L, N, E, F, K, T)는 반복할 수 없다.
더 큰 값의 글자 뒤에 하나 이상의 글자가 오면 그 값들을 더하며, 글자는 큰 값에서 작은 값 순서로 적는다. 예를 들어 FXVIII = 50000 + 10 + 5 + 1 + 1 + 1 = 50018 이다.
더 큰 값의 글자 앞에 어떤 글자가 오면 그 값을 빼며, 뺄 수 있는 글자는 최대 하나뿐이다. 예를 들어:
- XIV = 10 + (5 - 1) = 14
- CIX = 100 + (10 - 1) = 109
- MECIX = (5000 - 1000) + 100 + (10 - 1) = 4109
뺄 때 사용할 수 있는 글자는 10의 거듭제곱을 나타내는 글자뿐이다(V에서 I를, L에서 X를 뺄 수는 있지만, V는 10의 거듭제곱이 아니므로 X에서 V를 뺄 수는 없다).
열 배보다 더 큰 글자에서 빼는 것은 허용되지 않는다(X에서 I는 뺄 수 있지만 L에서 I는 뺄 수 없으므로, IL 같은 수는 존재하지 않는다).

이 규칙들에 의해 모든 십진수는 정확히 하나의 판다 수 표현을 가진다.

로마 숫자와 달리 판다는 0과 음수를 인식한다(판다가 고대 로마인보다 더 발전했다는 증거다). 음수는 글자들 앞에 대나무 하나를 음의 부호로 놓아 나타낸다. 0은 위의 어떤 규칙도 따르지 않는 특별한 수이며, 0을 만들려면 대나무 다섯 개가 필요하다.

어떤 수를 만드는 데 필요한 대나무의 개수는 그 수에 나타나는 각 글자에 필요한 대나무 개수의 합이다. 예를 들어:

두 수 A와 B가 주어질 때, A부터 B까지(양 끝 포함) 모든 수를 만드는 데 판다에게 필요한 대나무의 총 개수를 구하라.

첫째 줄에 테스트 케이스의 수를 나타내는 양의 정수 $T$ 가 주어진다. 이어지는 $T$ 개의 각 줄에는 두 정수 $A$ 와 $B$ 가 주어진다 ( $-25{,}000{,}000 \le A \le B \le 25{,}000{,}000$ ).

각 테스트 케이스마다, $A$ 부터 $B$ 까지(양 끝 포함) 모든 수를 만드는 데 필요한 대나무의 총 개수를 한 줄에 하나씩 출력한다.

예제 1

입력

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

예상 출력