11226 - Reaching the fix-point.

對於所有的整數 n (n > 1)，皆有唯一的一組質因數分解，例如4=2x2, 5=5, 6=2x3。

令sopf(n)表示 n 的所有質因數的總和，例如sopf(4) = 2 + 2 = 4, sopf(5) = 5, sopf(6) = 2 + 3 = 5。

由一個整數 n 開始，我們藉由sopf(n)找到下一個整數，再透過sopf(sopf(n))找到下下一個整數，以此類推，直到找到一數 f 使得 f = sopf(f)。例如由8開始，sopf(8) = 2 + 2 + 2 = 6，sopf(6) = 2 + 3 = 5，sopf(5) = 5，得到數列：8, 6, 5, 5, 5, ...。此數列共有3個不同的數值。

另外再定義 lsopf(n) 表示由 n 開始找出下一個sopf()直到重複為止，共有幾個數值，例如 lsopf(8) = 3, lsopf(4) = 1。

本題給定兩個自然數 n, m (1 < n, m)，請你找出介於 n 與 m 之間最大的 lsopf 之值。

Input

輸入資料的第一列有一個整數T(1 <= T <= 150)表示測試資料的組數，每組資料一列有兩個整數分別表示 n 與 m (1 <= n, m <= 500000)。

Output

請參考範列資料輸出格式，輸出其資料編號與介於 n, m 之間最大的 lsopf 之值。

Sample input

2
2 10
11 20

Sample output

Case #1:
3
Case #2:
4

---

原文出處