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.io.*;
import java.time.*;
import static java.lang.Math.*;

@SuppressWarnings("unused")
public class B {
	static boolean DEBUG = false;

	static int pre[][] = new int[30][2_000_00 + 5];
	static SegTree st[] = new SegTree[30];
	static int counter = 0;
	public static void main(String[] args) throws IOException {
		Instant start = Instant.now();
		if (args.length == 2) {
			System.setIn(new FileInputStream(new File("D:\\program\\javaCPEclipse\\CodeForces\\src\\input.txt")));
			// System.setOut(new PrintStream(new File("output.txt")));
			System.setErr(new PrintStream(new File("D:\\program\\javaCPEclipse\\CodeForces\\src\\error.txt")));
			DEBUG = true;
		}
		Reader fs = new Reader();
		PrintWriter pw = new PrintWriter(System.out);
		for (int i = 0; i < 2_000_00 + 5; i++) {
			pre[0][i] = i;
		}
		for (int i = 1; i < 30; i++) {
			for (int j = 0; j < 2_000_00 + 5; j++) {
				pre[i][j] = pre[i - 1][j] >> 1;
			}
		}
		long sum[][] = new long[30][2_00_000  + 5];
		for(int i =0 ; i < 30 ; i++) {
			sum[i][0] = pre[i][0] % 2;
			for(int j = 1 ; j < pre[i].length; j++) {
				sum[i][j] = (long)pre[i][j] % 2 + (long)sum[i][j-1];
			}
		}
		int t = fs.nextInt();
		for (int tt = 1; tt <= t; tt++) {
			int l = fs.nextInt();
			int r = fs.nextInt();
			int ans = Integer.MAX_VALUE;
			int n = (r - l + 1);
			for (int i = 0; i < 30; i++) {
				long x = sum[i][r] - sum[i][l-1];
				ans = min(ans, n - (int)x);
			}
			pw.println(ans);
		}
		Instant end = Instant.now();
		if (DEBUG) {
			pw.println(Duration.between(start, end));
		}
		pw.close();
	}

	static class SegTree {
		int leftmost, rightmost;
		int ans;
		SegTree lchild, rchild;

		public SegTree(int l, int r) {
			leftmost = l;
			rightmost = r;
			if (l == r) {
				ans = pre[counter][l] % 2;
			} else {
				int mid = (l + r) / 2;
				lchild = new SegTree(l, mid);
				rchild = new SegTree(mid + 1, r);
			}
			recalc();
		}

		public void recalc() {
			if (leftmost == rightmost) {
				return;
			}
			ans = lchild.ans + rchild.ans;
		}

		public int Query(int l, int r) {
			if (l > rightmost || r < leftmost)
				return 0;
			if (l <= leftmost && r >= rightmost)
				return ans;
			return lchild.Query(l, r) + rchild.Query(l, r);
		}
	}

	static void log(Object o) {
		if (DEBUG)
			System.err.println(o);
	}

	static void log(int a[]) {
		if (DEBUG)
			System.err.println(Arrays.toString(a));
	}

	static void log(char a[]) {
		if (DEBUG)
			System.err.println(Arrays.toString(a));
	}

	static void log(String a) {
		if (DEBUG)
			System.err.print(a + " -> ");
	}

	static <T> void log(T a[]) {
		if (DEBUG) {
			System.err.print("[");
			for (T x : a)
				System.err.print(x + " ");
			System.err.println("]");
		}
	}

	static <T> void log(ArrayList<T> a) {
		if (DEBUG) {
			System.err.print("[");
			for (T x : a) {
				System.err.print(x + " ");
			}
			System.err.println("]");
		}
	}

	static <T, V> void log(Map<T, V> mp) {
		if (DEBUG) {
			System.err.print(mp);
		}
	}

	public static void print(long a, long b, long c, PrintWriter pw) {
		pw.println(a + " " + b + " " + c);
		return;
	}

	static class Reader {
		BufferedReader br;
		StringTokenizer st;

		public Reader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		String next() {
			while (st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}

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

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

		double nextDouble() {
			return Double.parseDouble(next());
		}

		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch (IOException e) {
				e.printStackTrace();
			}
			return str;
		}

		int[] readArray(int n) {
			int a[] = new int[n];
			for (int i = 0; i < n; i++)
				a[i] = nextInt();
			return a;
		}

		int[][] read2Array(int n, int m) {
			int a[][] = new int[n][m];
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < m; j++) {
					a[i][j] = nextInt();
				}
			}
			return a;
		}
	}
}