D2. Xor-Subsequence (hard version)
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output
It is the hard version of the problem. The only difference is that in this version ai≤109ai≤109.
You are given an array of nn integers a0,a1,a2,…an−1a0,a1,a2,…an−1. Bryap wants to find the longest beautiful subsequence in the array.
An array b=[b0,b1,…,bm−1]b=[b0,b1,…,bm−1], where 0≤b0 Subsequence b=[b0,b1,…,bm−1]b=[b0,b1,…,bm−1] of length mm is called beautiful, if the following condition holds: Here a⊕ba⊕b denotes the bitwise XOR of aa and bb. For example, 2⊕4=62⊕4=6 and 3⊕1=23⊕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. Input The first line contains a single integer tt (1≤t≤1051≤t≤105) — the number of test cases. The description of the test cases follows. The first line of each test case contains a single integer nn (2≤n≤3⋅1052≤n≤3⋅105) — the length of the array. The second line of each test case contains nn integers a0,a1,...,an−1a0,a1,...,an−1 (0≤ai≤1090≤ai≤109) — the elements of the array. It is guaranteed that the sum of nn over all test cases does not exceed 3⋅1053⋅105. Output For each test case print a single integer — the length of the longest beautiful subsequence.