SP22534 PRJAN15B - Birthday Gift for SJ

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 $ ^{2} $ , 8 = 2 $ ^{3} $ , 9 = 3 $ ^{2} $ 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 10 $ ^{5} $ - 1 10 $ ^{18} $ Sample Input Output for Sample Input 3 1 4 7 10 15 20 1 2 4

N/A

N/A