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