Practice on Toph

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

Complex Tashreef

By Tash52 · Limits 2s, 512 MB

Tashreef finally received the Zuinness Journal of Galactic records recognition for being the most complex thinker in the whole Milky Way galaxy!!

He will be participating in the intergalactic level next. To ensure the pride of our Milky Way many are helping him to become more and more complex by giving their assistance. His friend, Tashfiq has also been contributing, and he has given the following problem for him to solve!
Tashreef will be given two positive integers L and R. He needs to find the value of -

But the problem was too complex even for the legendary Tashreef. He asked you to help him solve this problem. Help him find the answer.

As the result can be very large, print the answer modulo 1000000007 (109+7)(10^{9} + 7)

Input

The first line will contain an integer T denoting the number of test cases. The next T lines will contain two integers each, L and R.

  • 1T21051 ≤ T ≤ 2 · 10^{5}
  • 0LR10140 ≤ L ≤ R ≤ 10^{14}

Output

For each test, output a single line “Case N: X” (without quotation), where N is the test number (starting from 1) and X is the answer (see examples for clarification).

Sample

InputOutput
5
78 100
34 67
12 25
34 34
55 61
Case 1: 1654
Case 2: 1253
Case 3: 171
Case 4: 31
Case 5: 261

Discussion

Statistics


88% Solution Ratio

YouKnowWhoEarliest, 6M ago

Deshi_TouristFastest, 0.2s

YouKnowWhoLightest, 4.6 MB

steinumShortest, 688B

Submit

Login to submit

Editorial

Editorial...

Toph uses cookies. By continuing you agree to our Cookie Policy.