B. And It's Non-Zero
bitmasks; greedy; math
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 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.
The first line contains one integer \(t\) (\(1 \leq t \leq 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 \leq l \leq r \leq 2 \cdot 10^5\)) — the description of the array.
For each test case, output a single integer — the answer to the problem.
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.