While doing some spring cleaning, Daniel found an old calculator that he loves so much. However, it seems like it is broken. When he tries to compute 1 + 3 using the calculator, he gets 2 instead of 4. But when he tries computing 1 + 4, he gets the correct answer, 5. Puzzled by this mystery, he opened up his calculator and found the answer to the riddle: the full adders became half adders! 

So, when he tries to compute the sum a + b using the calculator, he instead gets the xorsum a ⊕ b (read the definition by the link: <https://en.wikipedia.org/wiki/Exclusive_or>).

As he saw earlier, the calculator sometimes gives the correct answer. And so, he wonders, given integers l and r, how many pairs of integers (a, b) satisfy the following conditions: $$$a + b = a ⊕ b l ≤ a ≤ r l ≤ b ≤ r$$$

However, Daniel the Barman is going to the bar and will return in two hours. He tells you to solve the problem before he returns, or else you will have to enjoy being blocked.

Input

The first line contains a single integer t (1 ≤ t ≤ 100) — the number of testcases.

Then, t lines follow, each containing two space-separated integers l and r (0 ≤ l ≤ r ≤ 10^9).

Output

Print t integers, the i-th integer should be the answer to the i-th testcase.

Example

Input


3
1 4
323 323
1 1000000


Output


8
0
3439863766

Note

a ⊕ b denotes the bitwise XOR of a and b.

For the first testcase, the pairs are: (1, 2), (1, 4), (2, 1), (2, 4), (3, 4), (4, 1), (4, 2), and (4, 3).
/**
 * BaZ :D
 */
import java.lang.reflect.Array;
import java.util.*;
import java.io.*;
import static java.lang.Math.*;

public class Main
{
    static MyScanner scan;
    static PrintWriter pw;
    static long MOD = 1_000_000_007;
    static long INF = 1_000_000_000_000_000_000L;
    static long inf = 2_000_000_000;
    public static void main(String[] args) {
        new Thread(null, null, "BaZ", 1 << 27) {
            public void run() {
                try {
                    solve();
                } catch (Exception e) {
                    e.printStackTrace();
                    System.exit(1);
                }
            }
        }.start();
    }
    static long dp[][][][][];
    static int L, R;
    static void solve() throws IOException
    {
        //initIo(true);
        initIo(false);
        StringBuilder sb = new StringBuilder();
        int t = ni();
        dp = new long[31][2][2][2][2];
        while(t-->0) {
            L = ni();
            R = ni();
            for(int i=0;i<31;++i) {
                for(int j=0;j<2;++j) {
                    for(int k=0;k<2;++k) {
                        for(int l=0;l<2;++l) {
                            for(int m=0;m<2;++m) {
                                dp[i][j][k][l][m] = -1;
                            }
                        }
                    }
                }
            }
            pl(f(30, 0, 0, 0, 0));
        }
        pw.flush();
        pw.close();
    }
    static long f(int bit, int n1_is_greater_than_l, int n1_is_less_than_r, int n2_is_greater_than_l, int n2_is_less_than_r) {
        if(bit==-1) {
            return 1;
        }
        if(dp[bit][n1_is_greater_than_l][n1_is_less_than_r][n2_is_greater_than_l][n2_is_less_than_r] != -1) {
            return dp[bit][n1_is_greater_than_l][n1_is_less_than_r][n2_is_greater_than_l][n2_is_less_than_r];
        }
        long ans = 0;
        boolean can_append_0_to_n1 = (n1_is_greater_than_l == 1) || ((L&(1<<bit)) == 0);
        boolean can_append_1_to_n1 = (n1_is_less_than_r == 1) || ((R&(1<<bit)) != 0);
        boolean can_append_0_to_n2 =  (n2_is_greater_than_l == 1) || ((L&(1<<bit)) == 0);
        boolean can_append_1_to_n2 =  (n2_is_less_than_r == 1) || ((R&(1<<bit)) != 0);
        // 0 0

        if(can_append_0_to_n1 && can_append_0_to_n2) {
            ans+=f(
                    bit-1,
                    n1_is_greater_than_l,
                    n1_is_less_than_r | ( (R&(1<<bit)) !=0 ? 1 : 0),
                    n2_is_greater_than_l,
                    n2_is_less_than_r | ( (R&(1<<bit)) !=0 ? 1 : 0)
                    );
        }

        //1 0

        if(can_append_1_to_n1 && can_append_0_to_n2) {
            ans+=f(bit-1,
                    n1_is_greater_than_l | ((L&(1<<bit)) == 0 ? 1 : 0),
                    n1_is_less_than_r,
                    n2_is_greater_than_l,
                    n2_is_less_than_r | ( (R&(1<<bit)) !=0 ? 1 : 0));
        }


        //0 1

        if(can_append_0_to_n1 && can_append_1_to_n2) {
            ans+=f(bit-1,
                    n1_is_greater_than_l,
                    n1_is_less_than_r | ( (R&(1<<bit)) !=0 ? 1 : 0),
                    n2_is_greater_than_l | ((L&(1<<bit)) == 0 ? 1 : 0),
                    n2_is_less_than_r
                    );
        }

        return dp[bit][n1_is_greater_than_l][n1_is_less_than_r][n2_is_greater_than_l][n2_is_less_than_r] = ans;
    }
    static void initIo(boolean isFileIO) throws IOException {
        scan = new MyScanner(isFileIO);
        if(isFileIO) {
            pw = new PrintWriter("/Users/amandeep/Desktop/output.txt");
        }
        else {
            pw = new PrintWriter(System.out, true);
        }
    }
    static int ni() throws IOException
    {
        return scan.nextInt();
    }
    static long nl() throws IOException
    {
        return scan.nextLong();
    }
    static double nd() throws IOException
    {
        return scan.nextDouble();
    }
    static String ne() throws IOException
    {
        return scan.next();
    }
    static String nel() throws IOException
    {
        return scan.nextLine();
    }
    static void pl()
    {
        pw.println();
    }
    static void p(Object o)
    {
        pw.print(o+" ");
    }
    static void pl(Object o)
    {
        pw.println(o);
    }
    static void psb(StringBuilder sb)
    {
        pw.print(sb);
    }
    static void pa(String arrayName, Object arr[])
    {
        pl(arrayName+" : ");
        for(Object o : arr)
            p(o);
        pl();
    }
    static void pa(String arrayName, int arr[])
    {
        pl(arrayName+" : ");
        for(int o : arr)
            p(o);
        pl();
    }
    static void pa(String arrayName, long arr[])
    {
        pl(arrayName+" : ");
        for(long o : arr)
            p(o);
        pl();
    }
    static void pa(String arrayName, double arr[])
    {
        pl(arrayName+" : ");
        for(double o : arr)
            p(o);
        pl();
    }
    static void pa(String arrayName, char arr[])
    {
        pl(arrayName+" : ");
        for(char o : arr)
            p(o);
        pl();
    }
    static void pa(String listName, List list)
    {
        pl(listName+" : ");
        for(Object o : list)
            p(o);
        pl();
    }
    static void pa(String arrayName, Object[][] arr) {
        pl(arrayName+" : ");
        for(int i=0;i<arr.length;++i) {
            for(Object o : arr[i])
                p(o);
            pl();
        }
    }
    static void pa(String arrayName, int[][] arr) {
        pl(arrayName+" : ");
        for(int i=0;i<arr.length;++i) {
            for(int o : arr[i])
                p(o);
            pl();
        }
    }
    static void pa(String arrayName, long[][] arr) {
        pl(arrayName+" : ");
        for(int i=0;i<arr.length;++i) {
            for(long o : arr[i])
                p(o);
            pl();
        }
    }
    static void pa(String arrayName, char[][] arr) {
        pl(arrayName+" : ");
        for(int i=0;i<arr.length;++i) {
            for(char o : arr[i])
                p(o);
            pl();
        }
    }
    static void pa(String arrayName, double[][] arr) {
        pl(arrayName+" : ");
        for(int i=0;i<arr.length;++i) {
            for(double o : arr[i])
                p(o);
            pl();
        }
    }
    static class MyScanner
    {
        BufferedReader br;
        StringTokenizer st;
        MyScanner(boolean readingFromFile) throws IOException
        {
            if(readingFromFile) {
                br = new BufferedReader(new FileReader("/Users/amandeep/Desktop/input.txt"));
            }
            else {
                br = new BufferedReader(new InputStreamReader(System.in));
            }
        }
        String nextLine()throws IOException
        {
            return br.readLine();
        }
        String next() throws IOException
        {
            if(st==null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }
        int nextInt() throws IOException
        {
            return Integer.parseInt(next());
        }
        long nextLong() throws IOException
        {
            return Long.parseLong(next());
        }
        double nextDouble() throws IOException
        {
            return Double.parseDouble(next());
        }
    }
}