You are given a range of numbers from [A, B]. Let's define a good divisor of a number N to be the largest odd divisor of N. You have to find the sum of all good divisors from [A, B] (both inclusive).

Input

• The first line contains the number of test cases T.
• Each line of the test case contains two integers A and B respectively.

Output

• For each test case print in a new line the answer to that test case. i.e. the sum of all good divisors from [A, B] (both inclusive).

Constraints

• 1 <= T <= 10⁵
• 1 <= A <= B <= 10⁹

Scoring

Scores will be calculated as follows:

Score = (1 - c / 2000) * 150, where c is the number of characters in your code. In case the characters exceed 2000, your score will be zero.