CF1720D2 Xor-Subsequence (hard version)

It is the hard version of the problem. The only difference is that in this version $ a_i \le 10^9 $ . You are given an array of $ n $ integers $ a_0, a_1, a_2, \ldots a_{n - 1} $ . Bryap wants to find the longest beautiful subsequence in the array. An array $ b = [b_0, b_1, \ldots, b_{m-1}] $ , where $ 0 \le b_0 < b_1 < \ldots < b_{m - 1} < n $ , is a subsequence of length $ m $ of the array $ a $ . Subsequence $ b = [b_0, b_1, \ldots, b_{m-1}] $ of length $ m $ is called beautiful, if the following condition holds: - For any $ p $ ( $ 0 \le p < m - 1 $ ) holds: $ a_{b_p} \oplus b_{p+1} < a_{b_{p+1}} \oplus b_p $ . Here $ a \oplus b $ denotes the [bitwise XOR](https://en.wikipedia.org/wiki/Bitwise_operation#XOR) of $ a $ and $ b $ . For example, $ 2 \oplus 4 = 6 $ and $ 3 \oplus 1=2 $ . Bryap is a simple person so he only wants to know the length of the longest such subsequence. Help Bryap and find the answer to his question.

The first line contains a single integer $ t $ ( $ 1 \leq t \leq 10^5 $ ) — the number of test cases. The description of the test cases follows. The first line of each test case contains a single integer $ n $ ( $ 2 \leq n \leq 3 \cdot 10^5 $ ) — the length of the array. The second line of each test case contains $ n $ integers $ a_0,a_1,...,a_{n-1} $ ( $ 0 \leq a_i \leq 10^9 $ ) — the elements of the array. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 3 \cdot 10^5 $ .

For each test case print a single integer — the length of the longest beautiful subsequence.

In the first test case, we can pick the whole array as a beautiful subsequence because $ 1 \oplus 1 < 2 \oplus 0 $ . In the second test case, we can pick elements with indexes $ 1 $ , $ 2 $ and $ 4 $ (in $ 0 $ indexation). For this elements holds: $ 2 \oplus 2 < 4 \oplus 1 $ and $ 4 \oplus 4 < 1 \oplus 2 $ .