Nakochi and Numbers
Time Limit: 12000ms
Memory Limit: 65536kb
DescriptionNakochi is lovely girl. She loves numbers. But recently, she gets annoyed by a number 23333.
As we all know, 23333 is widely used in the Internet. Nakochi don't like any number which only contains digits 2 and 3 in decimal. She call them bad number. And she defines two functions: pre(x), next(x), which means the largest bad number which is no more than x, and the smallest bad number which is no less than x. And she wonders the value of the following function:
InputThis problem contains multiple tests. The first line there will be a number T which means how many test cases in the final test. After that there will be T lines. Each line contains two numbers L and R. (You can assume 2<=L <= R<= 1e18, 1<=T<= 200).
OutputOutput the answer module 1000000007.
2 2 3 3 10
Hintnext(2) = 2, pre(2) = 2, next(3) = 3, pre(3) = 3, next(7) = 22, pre(7) = 3;