Description

Mathematicians like numbers with various strange properties. For example, they consider $945$ an interesting number because it is the first odd number whose sum of all divisors is greater than itself.

To help them find interesting numbers, you will write a program to scan numbers within a given range and determine the number in this range that has the most divisors. Unfortunately, both the number and the given range can be large, and using a simple approach may take a lot of time. So please ensure your algorithm can finish scanning the maximum range within a few seconds.

Input Format

A single line giving the range to scan, specified by the lower bound $L$ and upper bound $U$, satisfying $2 \le L \le U \le 10^9$.

Output Format

For the given range, output the number $P$ in this range that has the maximum number of divisors $D$. If there are multiple, output the smallest one. Please output $\texttt{Between }L\texttt{ and }U\texttt{, }P\texttt{ has a maximum of }D\texttt{ divisors.}$, where $L$, $U$, $P$, and $D$ have the meanings stated above.

1000 2000

Between 1000 and 2000, 1680 has a maximum of 40 divisors.

Hint

update: 2024/6/6 added 6 hack testcases.

Translated by ChatGPT 5