2012年12月23日 星期日

11876 - N + NOD (N)


考慮一正整數的數列 N,其中:

$N_0=1$
$N_i=N_{i-1}+NOD(N_{i-1}), \text{ for } i>0$

在這裡,NOD(x) = x 因數的個數。

因此,這個數列的前幾項為:1, 2, 4, 7, 9, 12, 18, …

給兩個正整數 A 和 B,請找出數列中範圍介於 [A, B] 中整數的個數。

輸入

輸入的第一行有一正整數 T($T<100000$),代表測試資料的組數。每組測資包含兩個整數 A 和 B($1{\leq}A{\leq}B{\leq}1000000$)。

輸出

對於每組測資,輸出是第幾組測資和要求的答案。

範例輸入

3
1 18
1 100
3000 4000

範例輸出

Case 1: 7
Case 2: 20
Case 3: 87


Problemsetter: Sohel Hafiz, Special Thanks: Shamim Hafiz