11876 - N + NOD (N)

考慮整數序列：

N₀ = 1
N_i = N_i-1 + NOD(N_i-1)- for i > 0

其中，NOD(x)表示能整除 x 的除數(因數)個數。所以序列的前幾項為1 2 4 7 9 12 18...。給定兩個整數A與B，請輸出序列中數值大小介於[A, B]之間的整數個數。

Input

輸入的第一列有一個整數T (T < 100000)表示測試資料的組數，每組資料有兩個整數A, B(1 <= A <= B <= 1000000)。

Output

請參考範例資料格式，輸出編號與答案。

Sample Input	Sample Output
3 1 18 1 100 3000 4000	Case 1: 7 Case 2: 20 Case 3: 87

---

原文出處