H. Median Gcd
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a whiteboard with integers from $$$l$$$ to $$$r$$$ written on it, inclusive. Initially, the whiteboard contains the set of integers $$$\{l, l+1, \dots, r\}$$$. You will repeatedly perform the following two operations until the whiteboard is empty:

  1. Add the greatest common divisor (GCD) of all numbers currently on the whiteboard to your total score.
  2. Remove the median element from the whiteboard. The median of a set of $$$n$$$ elements is defined as the element at index $$$\lfloor \frac{n+1}{2} \rfloor$$$ when the elements are sorted in non-decreasing order. For example, if the elements are $$$\{2, 5, 1, 8, 3\}$$$, sorted they are $$$\{1, 2, 3, 5, 8\}$$$. Here $$$n=5$$$, $$$\lfloor \frac{5+1}{2} \rfloor = 3$$$. The element at index 3 (1-indexed) is 3, so the median is 3.

Your task is to calculate the final total score after the whiteboard becomes empty.

Input

The first line contains an integer $$$T$$$ ($$$1 \le t \le 10^5$$$), the number of testcases. Each of the following $$$t$$$ lines contains two integers $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le 2 \times 10^9$$$).

Output

For each testcase, print a single integer representing the final total score.

Example
Input
2
1 3
3 5
Output
5
7