Complex Tashreef

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 $(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.

• $1 ≤ T ≤ 2 · 10^{5}$
• $0 ≤ 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

Input	Output
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