Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

A Girl Has No Name

By rezaulhsagar · 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.

1 ≤ T ≤ 10
1 ≤ L ≤ R ≤ 107

1 ≤ T ≤ 5
1 ≤ L ≤ R ≤ 1014

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```

Statistics

14% Solution Ratio

YouKnowWhoEarliest, 4w ago

YouKnowWhoFastest, 0.9s

JisangainLightest, 426 MB

omar24Shortest, 1524B