Since \(\gcd(L,L+1)=1\), there is always a solution.

We can just try all pairs \((x,y)\) such that \(L \leq x < y \leq R\) in decreasing order of \((y-x)\) and print \((y-x)\) when we have \(\gcd(x,y)=1\).

The correctness of this method is obvious, so let us estimate the complexity. We are going to try \(O(K^2)\) pairs, where \(K\) is the difference between \(R-L\) and the answer. Taking account of the time to compute gcd, the total complexity is \(O(K^2 \log R)\), so we are done if we can show that \(K\) is small.

One way to prove it is to use prime gap.

Under the Constraints of this problem, \(1500\) consecutive integers always contain at least one prime. Thus, among \((x,y)=(L,R),(L,R-1),\cdots,(L,R-1500)\), at least one satisfies \(\gcd(x,y)=1\). This shows \(K \leq 1500\).

Sample Submission (C++)

In fact, \(K\) will be much smaller than this limit. Among \(R-5, \cdots, R\), there is always a number coprime with \(30\), which, under the Constraints, is always coprime with some of \(L, \cdots, L+16\). This shows \(K \leq 21\). (Proof by maspy) It is possible to generate a case with \(K=7\) using CRT. (The idea of shuffling primes was proposed by Nyaan)