***Super Numbers Solved

Super Numbers

Euler's phi function for a positive integer N is usually denoted as φ(N) and defined as the number of positive integers less than or equal to N that are coprime with N. Let's call a positive integer N a super number if Ncan be divided by φ(N) without a remainder. 
e.g. 2 is a super number (since 2 mod φ(2) = 0), while 3 is not (since 3 mod φ(3) = 1).

You are given two positive integers L and R. Your task is to find count of super numbers in the range [L, R].

Input

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.

Each test case is described by a single line containing two positive integers L and R.

Output

For each test case, output a single line containing one integer: the number of super numbers in the range.

Constraints

• 1 ≤ T ≤ 1000
• 1 ≤ L ≤ R ≤ 10¹⁸

Example

Input:
3
2 3
90 95
12 21

Output:
1
0
3

Explanation

In the first example, 2 is a super number while 3 is not (as explained in the statement). So, the number of super numbers in the range [2, 3] will be equal to 1.

-----------------------------------------------------------------------------------------editorial-----------------------------------------------------------

 all no b/w L to R which are in the form of 2^a *3^b are give n%phi(n)==0

where a>=1 and b>=0

-------------------------------------------------------------------------------code---------------------------------------------------------------------------

#include<iostream>

#include<bits/stdc++.h>

using namespace std;

 typedef unsigned long long int lli;

 typedef long int li;

#define pp pair<pair<lli,int>,int> >

 #define ff first

 #define ss second

 int dx[]={1,-1,0,0};

 int dy[]={0,0,-1,1};

 #define mp make_pair

 #define pb push

lli two[100];

lli three[1000];

lli calc(int i,int j)

 {

 return pow(2,i)*pow(3,j);

 }

int  main()

 {

  int t;

  cin>>t;

   while(t--)

    {

     lli l,r;

      cin>>l>>r;

      lli c=l;

       two[0]=1;

       three[0]=1;

        for(int i=1;i<=59;i++)

         {

          two[i]=two[i-1]*2;

          three[i]=three[i-1]*3;

 }

      

      

       lli cc=0;

        if(l==1) cc++;

        for(int i=1;i<=59;i++)

         {

          for(int j=0;j<=37;j++)

           {

             lli fii=calc(i,j);

             if(fii>=l && fii<=r) cc++;

 

}

 }

 

  cout<<cc<<endl;

}

  return 0;

 }