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).
import java.math.BigDecimal;
import java.math.BigInteger;
import java.math.RoundingMode;
import java.util.*;
import java.io.*;
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////                                                                                                               /////////
////////                                                                                                               /////////
////////   HHHH        HHHH  EEEEEEEEEEEEE   MMMM          MMMM         OOOOOO             SSSSSSS      EEEEEEEEEEEEE  /////////
////////   HHHH        HHHH  EEEEEEEEEEEEE   MMMMMM      MMMMMM      OOO      OOO        SSSS   SSS     EEEEEEEEEEEEE  /////////
////////   HHHH        HHHH  EEEEE           MMMM MMM  MMM MMMM    OOO          OOO    SSSS       SSS   EEEEE          /////////
////////   HHHH        HHHH  EEEEE           MMMM  MMMMMM  MMMM   OOO            OOO   SSSS             EEEEE          /////////
////////   HHHH        HHHH  EEEEE           MMMM          MMMM  OOO              OOO   SSSSSSS         EEEEE          /////////
////////   HHHHHHHHHHHHHHHH  EEEEEEEEEEE     MMMM          MMMM  OOO              OOO      SSSSSS       EEEEEEEEEEE    /////////
////////   HHHHHHHHHHHHHHHH  EEEEEEEEEEE     MMMM          MMMM  OOO              OOO         SSSSSSS   EEEEEEEEEEE    /////////
////////   HHHH        HHHH  EEEEE           MMMM          MMMM   OOO            OOO              SSSS  EEEEE          /////////
////////   HHHH        HHHH  EEEEE           MMMM          MMMM    OOO          OOO     SSS       SSSS  EEEEE          /////////
////////   HHHH        HHHH  EEEEEEEEEEEEE   MMMM          MMMM      OOO      OOO        SSS    SSSS    EEEEEEEEEEEEE  /////////
////////   HHHH        HHHH  EEEEEEEEEEEEE   MMMM          MMMM         OOOOOO             SSSSSSS      EEEEEEEEEEEEE  /////////
////////                                                                                                               /////////
////////                                                                                                               /////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

public class Contest1 {
    static int mod= (int) (1e9+7);
    static char[]s,s2;
    static long[][][][][]memo;
    static long dp(int fl,int fr,int sl,int sr,int idx){
        if (idx==35)return 1;
        if (memo[fl][fr][sl][sr][idx]!=-1)return memo[fl][fr][sl][sr][idx];
        int l =s[idx]-'0';
        int r=s2[idx]-'0';
        long ans=0;
        for(int i =0;i<2;i++){
            for (int j=0;j<2;j++){
                if (i==1&&j==1)continue;
                if (!ok(l,r,fl,fr,i)||!ok(l,r,sl,sr,j))continue;
                ans+=dp(sml(l,fl,i),grt(r,fr,i),sml(l,sl,j),grt(r,sr,j),idx+1);
            }
        }
        return memo[fl][fr][sl][sr][idx]=ans;
    }
    static int grt(int r,int isr,int bit){
        if (isr==0)return isr;
        if (bit<r)return 0;
        return 1;
    }
    static int sml(int l,int isl,int bit){
        if (isl==0)return isl;
        if (bit>l)return 0;
        return 1;
    }
    static boolean ok(int l,int r,int isl,int isr,int bit){
        boolean f1=true;
        boolean f2=true;
        if (isr==1){
            f1=bit<=r;
        }
        if (isl==1){
            f2=bit>=l;
        }
        return f1&f2;
    }
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        PrintWriter pw = new PrintWriter(System.out);
        int n = sc.nextInt();
        while (n-->0){
            int l = sc.nextInt();
            int r = sc.nextInt();
            memo=new long[2][2][2][2][35];
            for (long[][][][]a:memo)
                for (long[][][]b:a)
                    for (long[][]c:b)
                        for (long[]d:c)
                            Arrays.fill(d,-1);

            char[]ss=Integer.toBinaryString(l).toCharArray();
            s=new char[35];
            Arrays.fill(s,'0');
            int id=ss.length-1;
            for (int i =34;i>=0;i--){
                if (id>=0){
                    s[i]=ss[id--];
                }
            }
            s2=new char[35];
            Arrays.fill(s2,'0');
            ss=Integer.toBinaryString(r).toCharArray();
            id=ss.length-1;
            for (int i =34;i>=0;i--){
                if (id>=0){
                    s2[i]=ss[id--];
                }
            }
//            pw.println(Arrays.toString(s));
            pw.println(dp(1,1,1,1,0));
        }
        pw.flush();
    }

    static int gcd(int a, int b) {
        if (a == 0) return b;
        return gcd(b % a, a);
    }

    static class Scanner {
        StringTokenizer st;
        BufferedReader br;

        public Scanner(InputStream s) {
            br = new BufferedReader(new InputStreamReader(s));
        }

        public Scanner(FileReader r) {
            br = new BufferedReader(r);
        }

        public String next() throws IOException {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }

        public int nextInt() throws IOException {
            return Integer.parseInt(next());
        }

        public long nextLong() throws IOException {
            return Long.parseLong(next());
        }

        public String nextLine() throws IOException {
            return br.readLine();
        }

        public double nextDouble() throws IOException {
            String x = next();
            StringBuilder sb = new StringBuilder("0");
            double res = 0, f = 1;
            boolean dec = false, neg = false;
            int start = 0;
            if (x.charAt(0) == '-') {
                neg = true;
                start++;
            }
            for (int i = start; i < x.length(); i++)
                if (x.charAt(i) == '.') {
                    res = Long.parseLong(sb.toString());
                    sb = new StringBuilder("0");
                    dec = true;
                } else {
                    sb.append(x.charAt(i));
                    if (dec)
                        f *= 10;
                }
            res += Long.parseLong(sb.toString()) / f;
            return res * (neg ? -1 : 1);
        }

        public boolean ready() throws IOException {
            return br.ready();


        }
    }
}