PRJAN15B - Birthday Gift for SJ

no tags 

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).

birthdayGift.jpg

Interesting numbers are:

  1. A number of the format xy. Where x >= 2 and y >= 2. For example, 4 = 22, 8 = 23, 9 = 32 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 ≤105
  • 1 ≤ a ≤ b ≤ 1018

Sample

Input:
3
1 4
7 10
15 20

Output:
1
2
4

Problem-Setter: Syed Shahriar Manjur



Added by:Shafaet
Date:2015-01-29
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 JS-MONKEY
Resource: Progrkriya Contest January 2015