정수론 싫어

정수론 중간고사를 마치고 집으로 돌아온 상근이는 패닉에 빠졌다. 유일하게 공부를 하지 않은 것이 오일러 피 함수(Euler's totient function, \(\varphi \))였는데, 그 함수에 관한 문제만 나왔기 때문이다. 상근이는 너무 억울했고, 직접 Totient 함수를 만들기로 했다.

정수론에서 양의 정수의 소인수는 그 정수를 나머지 없이 나눌 수 있는 소수이다. 상근이는 $n \ge 2$에서 함수 $F(n)$을 곱이 $n$이 되는 감소하지 않는 소수의 리스트로 정의했다. 예를 들어, $F(8) = \ll 2,2,2 \gg$, $F(60) = \ll 2,2,3,5 \gg$, $F(71) = \ll 71 \gg$ 이다. $O(n)$은 $F(n)$의 길이이다. 예를 들어, $O(8) = 3$, $O(60) = 4$, $O(71) = 1$ 이 된다. 마지막으로, 양의 정수에 대해서 \(p(n)\)을 다음과 같이 정의했다.

\(p(n) = \begin{cases} 0 & \text{if } n = 1 \\ -1 & \text{if } n \text{ is a prime number} \\ O(n) & \text {otherwise} \end{cases}\)

아래 표에는 \(p(n)\)의 첫 20개 값이 나와있다.

$a \le b$를 만족하는 두 양의 정수 $a$와 $b$에 대해서, 상근이는 자신의 Totient 함수인 \(\varphi(a,b)\)를 다음과 같이 정의했다.

\(\varphi (a,b)= ( \sum _{ k=a }^{ b }{ p(k) } ) - (b-a+1)\)

예를 들어, \(\varphi(1,4) = -4\), \(\varphi(16,16) = 3\), \(\varphi(8,12) = 4\) 이다.

구간 $\[L, U]$가 주어졌을 때, 가장 큰 값을 갖는 \(\varphi\)를 찾는 프로그램을 작성하시오.

즉, $L \le U$를 만족하는 두 양의 정수 $L$과 $U$가 주어졌을 때, 가장 큰 \(\varphi(a,b)\) ($L \le a \le b \le U$) 를 찾는 프로그램을 작성하시오. 예를 들어, 구간 $\[1,20]$에서 가장 큰 \(\varphi\)는 7이다. (\(\varphi(8,16)\))

입력은 7,000개 이하의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, $L$과 $U$가 주어진다. ($1 \le L \le U < 1,000,000$)

입력의 마지막 줄에는 $-1$이 두 개 주어진다.

각 테스트 케이스마다 주어진 구간 $\[L, U]$에서 찾을 수 있는 가장 큰 \(\varphi\) 값을 출력한다.