Limits 10s, 512 MB

"Joffrey... Cersei... Ilyn Payne... the Houn.." - Arya Stark

Garden of Bones, Game of Thrones S02E04

Arya Stark was one of the crucial member of the Stark family in the HBO's epic fantasy television series Game of Thrones.

Arya had a kill list consisting of a few people who had contributed to making her life stressful. But she is so young that she can not kill a man yet. She decided to go to Braavos to adopt some magical skills.

Arya's tutor gave him a huge task. She had to run a magic code in her computer.

func (L, R){
    sum = 0
    for (i = L; i <= R; i++){
        sum += score (i)
    }
    return sum
}

Where,

score (N){
    A = number of unique non zero digits of N
    B = number of unique digits of N which evenly divides N
    return power (B, A)    //B to the power A
}

She ran the code on her computer smoothly by some magical power. Can you do the same?

Input

Input starts with an integer T, denoting the number of test cases. Each case starts with a line containing two integers L R.

Scoring

Subtask 1 (20 Points): 1 ≤ T ≤ 10 1 ≤ L ≤ R ≤ 107

Subtask 2 (40 Points): 1 ≤ T ≤ 5 1 ≤ L ≤ R ≤ 1014

Subtask 3 (40 Points): T = 1 1 ≤ L ≤ R ≤ 1018

Output

For each case, print func (L, R) modulo (109 + 7)

Sample

InputOutput
3
1 10
12 15
20 100000
10
10
2522331

Submit

Login to submit.

Statistics

22% Solution Ratio
YouKnowWhoEarliest, Mar '20
mbsabbirr127Fastest, 0.3s
n3wb13_223Lightest, 364 MB
nfs277Shortest, 1288B
Toph uses cookies. By continuing you agree to our Cookie Policy.