提示: 欢迎访问OurACM平台。因与高数考试冲突,校赛改为5月6日13:00-17:00
Problem 1051 Divisors

Accept: 24    Submit: 242
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

Mathematicians love all sorts of odd properties of numbers. For instance, they consider 945 to be an interesting number, since it is the first odd number for which the sum of its divisors is larger than the number itself.

To help them search for interesting numbers, you are to write a program that scans a range of numbers and determines the number that has the largest number of divisors in the range. Unfortunately, the size of the numbers, and the size of the range is such that a too simple-minded approach may take too much time to run. So make sure that your algorithm is clever enough to cope with the largest possible range in just a few seconds.

Input

The first line of input specifies the number N of ranges, and each of the N following lines contains a range, consisting of a lower bound L and an upper bound U, where L and U are included in the range. L and U are chosen such that 1<=L<=U<=10^9 and 0<=U-L<=100000.

Output

For each range, output the largest number of divisors in the range.

Sample Input

3 1 10 1000 1000 999999900 1000000000

Sample Output

4 16 192

Submit  Back  Status  Discuss