I Hate Number Theory

After a number-theory midterm, a student who had skipped exactly one topic, Euler's totient function ($\varphi$), was dismayed to find every question was about it. So the student decided to define a personal totient function.

For an integer $n \ge 2$, let $F(n)$ be the non-decreasing list of primes whose product is $n$. For example, $F(8) = \langle 2, 2, 2 \rangle$, $F(60) = \langle 2, 2, 3, 5 \rangle$, and $F(71) = \langle 71 \rangle$. Let $O(n)$ be the length of $F(n)$, i.e. the number of prime factors of $n$ counted with multiplicity. Thus $O(8) = 3$, $O(60) = 4$, and $O(71) = 1$.

Now, for a positive integer $n$, define $p(n)$ as follows.

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

The table below lists the first $20$ values of $p(n)$.

For two positive integers $a$, $b$ with $a \le b$, define the totient function $\varphi(a, b)$ as follows.

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

For example, $\varphi(1, 4) = -4$, $\varphi(16, 16) = 3$, and $\varphi(8, 12) = 4$.

Given an interval $[L, U]$, write a program that finds the maximum value of $\varphi(a, b)$ over all $a$, $b$ with $L \le a \le b \le U$. For instance, over the interval $[1, 20]$ the maximum is $7$, attained at $\varphi(8, 16)$.

The input consists of several test cases, at most $7\,000$ of them. Each test case is a single line containing two integers $L$ and $U$. ($1 \le L \le U < 1\,000\,000$)

The last line contains two values of $-1$; this line is not processed.

For each test case, print on its own line the maximum value of $\varphi(a, b)$ obtainable over the interval $[L, U]$. Each line has the form <test case number>. <maximum>, where the test case number is counted from $1$.