Scoring Pairs

All submissions for this problem are available.
### Read problem statements in [Hindi](http://www.codechef.com/download/translated/DEC19/hindi/APAIRS.pdf), [Bengali](http://www.codechef.com/download/translated/DEC19/bengali/APAIRS.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/DEC19/mandarin/APAIRS.pdf), [Russian](http://www.codechef.com/download/translated/DEC19/russian/APAIRS.pdf), and [Vietnamese](http://www.codechef.com/download/translated/DEC19/vietnamese/APAIRS.pdf) as well. Chef likes assigning scores to pairs of numbers in an unusual way:  Consider a pair $(X, Y)$ of integers in decimal representation. If they don't have the same number of digits, add leading zeros to the smaller of these integers until they have the same number of digits. Let's denote the number of digits in each of the resulting decimal representations by $D$.  Reorder the digits of $Y$ in an arbitrary way.  For each $i$ ($1 \le i \le D$), calculate the absolute difference between the $i$th digit of $X$ and the $i$th digit of $Y$, and sum up these differences.  The score of the pair $(X, Y)$ is the minimum possible value of this sum. Consider the pair $(3178, 10920)$ as an example. The scoring procedure would be:  Add a leading zero to $X$, so the decimal representations are "03178" and "10920".  Reorder "10920" e.g. to "01029".  The score is $00 + 31 + 10 + 72 + 89 = 9$, since it is impossible to achieve a smaller sum. Now, Chef has a range $[L, R]$, and he wants to calculate the sum of scores of all pairs of integers in this range ― formally, $\sum_{i=L}^{R} \sum_{j=L}^{R} \mathrm{score}(i, j)$. Since he is very busy with all his problem cooking, he asks you to write a program that would compute this sum. Since it could be very large, compute it modulo $1,000,000,007$. ### Input  The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.  The first and only line of each test case contains two spaceseparated integers $L$ and $R$. ### Output For each test case, print a single line containing one integer ― the sum of scores modulo $1,000,000,007$. ### Constraints  $1 \le T \le 50$  $1 \le L \le R \le 10^{18}$ ### Subtasks **Subtask #1 (10 points):** $R \le 10^3$ **Subtask #2 (40 points):** $R \le 10^9$ **Subtask #3 (20 points):** $R \le 10^{12}$ **Subtask #4 (30 points):** original constraints ### Example Input ``` 2 1 10 3 17 ``` ### Example Output ``` 312 724 ```Author:  foyaz05 
Editorial  https://discuss.codechef.com/problems/APAIRS 
Tags  bruteforce, dec19, digitdp, foyaz05, mediumhard, melfice, probability 
Date Added:  8102019 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, SQL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 