정수론 싫어

정수론 중간고사가 끝났지만, 하필 공부하지 못한 오일러 피 함수($\varphi$)에서만 문제가 나와 곤란해진 한 학생이 직접 자신만의 Totient 함수를 정의하기로 했다.

$n \ge 2$인 정수에 대해, $F(n)$을 곱이 $n$이 되는 감소하지 않는 소수들의 리스트로 정의한다. 예를 들어 $F(8) = \langle 2, 2, 2 \rangle$, $F(60) = \langle 2, 2, 3, 5 \rangle$, $F(71) = \langle 71 \rangle$ 이다. $O(n)$은 $F(n)$의 길이, 즉 중복을 포함한 소인수의 개수이다. 따라서 $O(8) = 3$, $O(60) = 4$, $O(71) = 1$ 이다.

이제 양의 정수 $n$에 대해 $p(n)$을 다음과 같이 정의한다.

$p(n) = \begin{cases} 0 & (n = 1) \\ -1 & (n \text{ 이 소수}) \\ O(n) & (\text{그 외}) \end{cases}$

다음 표는 $p(n)$의 처음 $20$개 값이다.

$a \le b$인 두 양의 정수 $a$, $b$에 대해 Totient 함수 $\varphi(a, b)$를 다음과 같이 정의한다.

$\varphi(a, b) = \left( \sum_{k=a}^{b} p(k) \right) - (b - a + 1)$

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

구간 $[L, U]$가 주어졌을 때, $L \le a \le b \le U$를 만족하는 $a$, $b$ 중에서 $\varphi(a, b)$의 최댓값을 구하는 프로그램을 작성하시오. 예를 들어 구간 $[1, 20]$에서 최댓값은 $7$이며, 이는 $\varphi(8, 16)$에서 얻어진다.

입력은 여러 개의 테스트 케이스로 이루어지며, 테스트 케이스의 수는 최대 $7\,000$개이다. 각 테스트 케이스는 한 줄에 두 정수 $L$과 $U$로 주어진다. ($1 \le L \le U < 1\,000\,000$)

입력의 마지막 줄에는 $-1$이 두 개 주어지며, 이 줄은 처리하지 않는다.

각 테스트 케이스마다 한 줄씩, 구간 $[L, U]$에서 얻을 수 있는 $\varphi(a, b)$의 최댓값을 출력한다. 각 줄은 <테스트 케이스 번호>. <최댓값> 형식으로 출력하며, 테스트 케이스 번호는 $1$부터 순서대로 매긴다.