This problem was created by Clive Fraser and we are much grateful for it!
We will consider the digits from 0
to 9
and give each of them a weight, which is equal to the number of divisors of the digit. For this
purpose we will take the digit 0
to have a single divisor of 1
. The weights of the ten digits are as follows:
0
and 1
have a single divisor each, so have a weight of 1
.2
, 3
, 5
and 7
each have 2
divisors so their weight is 2
.4
and 9
each have 3
divisors and a weight of 3
.6
and 8
each have 4
divisors and a weight of 4
.Any integer n
has a Weighted Sum of Digits, which we will abbreviate to WSD(n)
, given by the sum of each digit in the number multiplied
by its weight. For example
WSD(9876543210) = 9x3 + 8x4 + 7x2 + 6x4 + 5x2 + 4x3 + 3x2 + 2x2 + 1x1 + 0x1 = 130.
Similarly WSD(868) = 88
and WSD(6) = 24
. We will further simplify the Weighted Sum of Digits by defining the short version W(n) = WSD(n) %10
.
In other words, W(n)
is simply the least significant digit of WSD(n)
. So W(9876543210) = 0
, W(868) = 8
and W(6) = 4
.
Next, consider the range of integers from 21
to 49
inclusive. The W(n)
values for these 29
integers are:
{5, 8, 0, 6, 4, 8, 8, 6, 1, 6, 7, 0, 2, 8, 6, 0, 0, 8, 3, 2, 3, 6, 8, 4, 2, 6, 6, 4, 9}.
The sum of these W(n)
values is 136
.
In this problem, you will be given several ranges of integer numbers. For each range you need to find the sum of the W(n)
values for each
number in the range (inclusive of the first and last integers in the range).
Input/Output description: The first line of the input data will contain a single integer N
, the number of ranges to process. N
lines
will follow. Each line contains two numbers n1
and n2
, separated by a space. Find the total of the W(n)
values for all numbers in the
range, from n1
to n2
inclusive. Combine all answers into a single string, separated by spaces.
Example:
input:
4
21 49
54 279
216 9335
5287 47076
answer:
136 1069 40284 186238