+ محدودیت زمان: ۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- روزی استادی وارد شهر شکرستان می‌شود. جمعی از دانش‌آموزان و دانش‌جویان نزد این استاد می‌روند و سوالات خود را از او می‌پرسند. "بهلول" نیز در میان دانش‌جویان نزد عالم می‌رود و سوال زیر را می‌پرسد :  اعداد زیبا اعدادی هستند که در نمایش مبنای $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 ```

حل سؤال در بانک سؤالات