318. A Bits of Fun

Problem Statement:
Coach Fegla is teaching students the Introduction to Computer Science course in lecture hall 260 in the Confucius Institute, Cairo University. Fegla believes that if the lecture hall looks nice and decorated with relevant decorations, it will boost the students' morale and enthusiasm to study and work harder in the course. Fegla told his trainees about what he was thinking and immediately Hossam Yousef - a trainee, that's all you have to know about him for now - suggested that Fegla decorates the hall with lots and lots of binary numbers. Fegla liked the idea, he decided to decorate the hall with consecutive numbers from A to B inclusive in their binary representation using 3D figures of zeroes and ones. Now, these are a lot of numbers and lots and lots of zeroes and ones - we are talking binary here, remember? - that means we need to use small 3D figures so we can fit all the numbers on the hall's walls. Luckily, Fegla has a huge stash of small 3D zero figures but he hasn't got a single one figure that's small, all of them were quite huge. Realizing this, Hossam offered helping Fegla and get him enough figures of the number one. Your task is to help Hossam. Given two integers A and B, calculate the number of ones in the binary representation of the numbers in the range A to B inclusive.

Input Format:
The input will start with an integer T which is the number of test cases where (1 ≤ T ≤ 100). Each test case consists of two integers, A and B where (1 ≤ A ≤ B ≤ 101000).

Output Format:
For each test case you should output "Case X: Y" where X is the case number starting from 1, and Y is the number of the one figures needed. Print the answer modulo 1, 000, 000, 007

Sample Input:
4 20 30 32 60 62 82 30 31

Sample Output:
Case 1: 35 Case 2: 96 Case 3: 67 Case 4: 9

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