322. The Last Digit

Problem Statement:
Who doesn?t just love meaningless problems with unbelievable stories? Because I know each one of you and I know how much you love meaningless problems, here?s another one (You don?t really have to thank me).

Mohamed Ahmed (AKA Nesr) just LOVES intellectual challenges. I remember when he drew lots of Tower-of-Hanoi towers to the extent that he was even cutting papers and collecting them together, just to try to solve it. That was in his first year. Now, Coach Fegla has just explained some Number Theory to the cute Nesr, and to tease him, he gave him this problem. To add some excitement, Coach Fegla wrote the problem as a function in pseudo code, and he asked Nesr to write an efficient function for that.

function LSD_FirstDigit(integer a, integer b) {
integer sum = 0;
for(integer i = a; i <= b; i++)
sum += (i * i);
return sum % 10; // '%' is the operator for getting remainder of division.
}

The variables here are NOT 32-bit integers. They could be infinitely-long integers. Please, help Nesr to solve it. Please, I beg you!

Input Format:
The input will start with an integer Q which is the number of queries where (1 ≤ Q ≤ 105). Each query consists of two integers, A and B, the inputs to the described function. (1 ≤ A ≤ B ≤ 1018).

Output Format:
For each query you should output "Case X: Y" where X is the case number starting from 1, and Y is the correct output of the described function.

Sample Input:
2 3 5 1 3

Sample Output:
Case 1: 0 Case 2: 4

Notes:
Note: G.H. Hardy, a Number Theorist, actually thought his work would never be of any use. You can bet how wrong he was. So, it seems like ?meaningless problems? are perhaps not all that meaningless after all.

 Added by: hossamyosef Added at: 2014-11-11 15:32:46 UTC Time Limit: 2 seconds Partial score: No Source: ACM Jordanian Collegiate Programming Contest 2014