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