B'It is the hard version of the problem. The only difference is that in this version a_i <= 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 <= 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: Here a oplus b denotes the bitwise 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 <= q t <= q 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 <= q n <= q 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 <= q a_i <= q 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 . '...