Divisors Again

For each of up to 10 ranges of at most 1001 integers, find the number in [L, U] with the most divisors.

Medium6Number theoryPrefix sumBrute forceNo attempts yetTime limit2sMemory limit512 MB

Description

Examples2

Problem

Count the divisors of every integer in the range $[L, U]$ and report the largest count. Both endpoints $L$ and $U$ belong to the range. A divisor count includes 1 and the number itself.

Input

The first line contains the number of ranges $C$ .

Each of the next $C$ lines contains the two endpoints $L$ and $U$ of one range, separated by a space.

Constraints

$1 \le C \le 10$
$1 \le L \le U \le 10^7$
$0 \le U - L \le 1000$

Output

For each range, print one line with the largest divisor count found in that range.