2011年12月17日 星期六

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

原文出處

沒有留言:

張貼留言