当前没有测试数据。

Today is your best friend SJ’s birthday. You want to buy a birthday present for her. You want to buy such a present that she likes the most. You are very superstitious. You think that, SJ will love your gift, if the price of the present you buy is an interesting number ( pretty weird isn’t it :P ).

Interesting numbers are :

1. A number of the format x^y. Where x>=2 and y>=2 . For example, 4= 2², 8 = 2³, 9 = 3² etc. are interesting numbers. Here x and y are integers.
2. Summation of two or more interesting numbers is also an interesting number. For example 13 = 9 + 4, 17 = 9+4+4 etc. are interesting numbers.

Input

The first line of the input is an integer t denoting the number of test cases. Then t line follows. Each line has two integers a and b.

Output

For each case you have to print a single line denoting the number of interesting numbers between a and b (inclusive).

Constraints

• 1 ≤ t ≤10⁵
• 1 ≤ a ≤ b ≤ 10¹⁸

Problem-Setter: Syed Shahriar Manjur