• محدودیت زمان: ۵ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

---

روزی استادی وارد شهر شکرستان می‌شود. جمعی از دانش‌آموزان و دانش‌جویان نزد این استاد می‌روند و سوالات خود را از او می‌پرسند. "بهلول" نیز در میان دانش‌جویان نزد عالم می‌رود و سوال زیر را می‌پرسد :

اعداد زیبا اعدادی هستند که در نمایش مبنای $10$ آنها، ارقام $0$ و $1$ وجود نداشته باشد. اگر عدد $n$ عددی زیبا باشد $p(n)$ را تعریف می‌کنیم برابر ضرب ارقام در نمایش مبنای $10$ عدد $n$ است.

اکنون $q(l, r)$ به این صورت تعریف می شود که چند عدد زیبا مانند $n$ وجود دارد به طوری که $l \leq p(n) \leq r$. به عبارت دیگر $q(l, r)$ برابر است با تعداد اعداد زیبایی که ضرب ارقام آن‌ها در بازه $[l, r]$ قرار می‌گیرد.

برای اینکه "بهلول" کار استاد را سخت‌تر کند به او $t$ بازه $[l, r]$ می‌دهد تا استاد باقی مانده‌ی جواب مسئله را برای هریک از این بازه‌ها را به $10 ^ 9 + 7$ برای این سوال بدست آورد. اکنون استاد که از این سوال حیرت‌زده می‌شود از شما می‌خواهد به او کمک کنید تا جواب سوال فوق را به "بهلول" بدهد.

ورودی

در خط اول ورودی یک عدد صحیح $t$ و در $t$ خط بعدی در هر خط دو عدد صحیح $l$ و $r$ به شما داده می شود.

$$1 \leq t \leq 1\ 000\ 000$$$$1 \leq l \leq r \leq 1\ 000\ 000\ 000\ 000 $$

خروجی

خروجی $t$ سطر دارد که برای هر کدام از $t$ بازه‌‌ی ورودی باقی‌مانده‌ی پاسخ مساله را به $10^9 + 7$ چاپ کنید.

مثال

ورودی نمونه ۱

10
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 10

خروجی نمونه ۱

0
1
1
2
1
3
1
4
2
2

ورودی نمونه ۲

10
5 10
2 3
9 10
3 8
5 10
4 6
2 3
3 5
1 7
1 10

خروجی نمونه ۲

13
2
4
12
13
6
2
4
9
17