You are given an array consisting of all integers from [l, r] inclusive. For example, if l = 2 and r = 5, the array would be [2, 3, 4, 5]. What's the minimum number of elements you can delete to make the [bitwise AND](https://en.wikipedia.org/wiki/Bitwise_operation#AND) of the array non-zero?

A bitwise AND is a binary operation that takes two equal-length binary representations and performs the AND operation on each pair of the corresponding bits.

Input

The first line contains one integer t (1 ≤ t ≤ 10^4) — the number of test cases. Then t cases follow.

The first line of each test case contains two integers l and r (1 ≤ l ≤ r ≤ 2 ⋅ 10^5) — the description of the array.

Output

For each test case, output a single integer — the answer to the problem.

Example

Input


5
1 2
2 8
4 5
1 5
100000 200000


Output


1
3
0
2
31072

Note

In the first test case, the array is [1, 2]. Currently, the bitwise AND is 0, as 1\ \& \ 2 = 0. However, after deleting 1 (or 2), the array becomes [2] (or [1]), and the bitwise AND becomes 2 (or 1). This can be proven to be the optimal, so the answer is 1.

In the second test case, the array is [2, 3, 4, 5, 6, 7, 8]. Currently, the bitwise AND is 0. However, after deleting 4, 5, and 8, the array becomes [2, 3, 6, 7], and the bitwise AND becomes 2. This can be proven to be the optimal, so the answer is 3. Note that there may be other ways to delete 3 elements.
import java.util.*;
import java.lang.*;
public class A {
 
	public static void main(String[] args) {
		
		Scanner input = new Scanner(System.in);
		
		int t = input.nextInt();

		int i,k,j,m;

		int[][] fin = new int[200002][20];
		for(j=1;j<=200000;j++) {


			String s = Long.toBinaryString(j);
			int num = s.length();
			//System.out.println(s+" "+num);
			int p = num-1;
			for(k=0;k<num;k++) {
				if(s.charAt(p)=='1') 
					fin[j][k]++;
				p--;

			}
			for(k=0;k<20;k++) 
				fin[j+1][k] = fin[j][k];

			

			//System.out.println(fin[j][0]+" "+fin[j][1]+" "+fin[j][2]);
		}
		
		
		for(i=0;i<t;i++) {
			int l = input.nextInt();
			int r = input.nextInt();
			

			
			int res = 0;
			int diff;
			for(j=0;j<20;j++) {
				if(l!=1)
					diff = fin[r][j] -fin[l-1][j];
				else
					diff = fin[r][j];
				
				res = Math.max(res, diff);
			}
			
			res = r-l+1-res;
			System.out.println(res);
			}
			
	}
		
		
	
	
	
	
	
	
	static long setbitNumber(long n)
    {
 
        
       long k = (int)(Math.log(n) / Math.log(2));
 
        
        return 1 << k;
    }
	
	static void leftrotate(int arr[],int i, int n)
    {
        int t = arr[i];
        int f;
        int j = i+1;
        for(;j<=n;j++) {
        	f = arr[j];
        	arr[j] = t;
        	t = f;
        	
        }
        arr[i] = t;
    }
	
	
	
	static int search(int l, int r,int x, int[]arr) {
		if (r >= l) {
            int mid = l + (r - l) / 2;
  
            
            if (arr[mid] == x)
                return mid;
  
           
            if (arr[mid] > x)
                return search( l, mid - 1, x,arr);
  
            
            return search( mid + 1, r, x,arr);
		}
		return -1;
	}
		
	
		
	static long coeff(int n, int k){    // nCr combination
		    
	    long res = 1;
	 

	        if (k > n - k)
	            k = n - k;
	 
	        // Calculate value of
	        // [n * (n-1) *---* (n-k+1)] / [k * (k-1) *----* 1]
	        for (int i = 0; i < k; ++i) {
	            res *= (n - i);
	            res /= (i + 1);
	        }
	 
	        return res;
	 }
	
	
	static long modpower(long x, long y, long p)
	  {
	    long res = 1; // Initialize result
	 
	    x = x % p; // Update x if it is more than or
	    // equal to p
	 
	    if (x == 0)
	      return 0; // In case x is divisible by p;
	 
	    while (y > 0)
	    {
	 
	      // If y is odd, multiply x with result
	      if ((y & 1) != 0)
	        res = (res * x) % p;
	 
	      // y must be even now
	      y = y >> 1; // y = y/2
	      x = (x * x) % p;
	    }
	    return res;
	  }
	
	
	static int xor(int n){
	        // If n is a multiple of 4
	        if (n % 4 == 0)
	            return n;
	      
	        // If n%4 gives remainder 1
	        if (n % 4 == 1)
	            return 1;
	      
	        // If n%4 gives remainder 2
	        if (n % 4 == 2)
	            return n + 1;
	      
	     return 0;
	 }
		
		
	static int getsum(int n)        // sum of digits
	   {    
	        int sum = 0;
	          
	        while (n != 0)
	        {
	            sum = sum + n % 10;
	            n = n/10;
	        }
	      
	   return sum;
	}
		
		
		
	static boolean isPrime(int n)			//  check prime
	    {
	 
	        if (n <= 1)
	            return false;
	        else if (n == 2)
	            return true;
	        else if (n % 2 == 0)
	            return false;
	 

	        for (int i = 3; i <= Math.sqrt(n); i += 2)
	        {
	            if (n % i == 0)
	                return false;
	        }
	        return true;
	    }
	
	static long gcd(long a, long b)
    {
        if (a == 0)
            return b;
        return gcd(b % a, a);
    }
 
		
	}	