修了大半個學期的競程之後，紅線決定要挑戰他的天才同學，他絞盡腦汁想了一個非常無聊、完全無意義的數列，然後跟那個天才吹噓他對這個數列已經可以倒背如流了！紅線原本的想法是寫一個程式來解，但是他這次是搬石頭砸自己的腳，因為這個數列實在有點複雜，導致他要向各位求救。
考慮一個整數數列：
a0 = 1
an = an-1 + NOD(an-1), for n > 0
其中，NOD(x)表示能整除x的因數個數(number of divisors)。所以此數列的前幾項依序為1, 2, 4, 7, 9, 12, 18...。給定兩個整數，A, B，請輸出此數列中數值大小介於[A, B]之間的整數個數。
輸入的第一列有一個整數T (T < 100,000)表示測試資料的組數，每組資料有兩個整數A, B(1 <= A <= B <= 1,000,000)。
每組測資一列，輸出其為第幾組測資與最後的答案。詳細輸出格式請參考範例測資。