D2. Xor-подпоследовательность (сложная версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. Единственное различие состоит в том, что в этой версии $$$a_i \le 10^9$$$.

Дан массив из $$$n$$$ целых чисел $$$a_0, a_1, a_2, \ldots a_{n - 1}$$$. Бряп захотел найти в данном массиве самую длинную хорошую подпоследовательность.

Массив $$$b = [b_0, b_1, \ldots, b_{m-1}]$$$, где $$$0 \le b_0 < b_1 < \ldots < b_{m - 1} < n$$$, будем называть подпоследовательностью длины $$$m$$$ массива $$$a$$$.

Подпоследовательность $$$b = [b_0, b_1, \ldots, b_{m-1}]$$$ длины $$$m$$$ называется хорошей, если выполняется следующее условие:

  • Для любого целого числа $$$p$$$ ($$$0 \le p < m - 1$$$) выполняется условие: $$$a_{b_p} \oplus b_{p+1} < a_{b_{p+1}} \oplus b_p$$$.

Здесь $$$a \oplus b$$$ обозначает побитовое исключающее ИЛИ чисел $$$a$$$ и $$$b$$$. Например, $$$2 \oplus 4 = 6$$$, а $$$3 \oplus 1=2$$$.

Так как Бряп не очень любознательная персона, он хочет знать лишь длину такой подпоследовательности. Помогите ему найти ответ на данную задачу.

Входные данные

Первая строка содержит единственное целое число $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит единственное целое число $$$n$$$ ($$$2 \leq n \leq 3 \cdot 10^5$$$) — длина массива.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_0,a_1,...,a_{n-1}$$$ ($$$0 \leq a_i \leq 10^9$$$) — элементы массива.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$3 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных единственное число — максимальную длину хорошей подпоследовательности.

Пример
Входные данные
3
2
1 2
5
5 2 4 3 1
10
3 8 8 2 9 1 6 2 8 3
Выходные данные
2
3
6
Примечание

В первом наборе входных данных в качестве подпоследовательности мы можем выбрать оба элемента массива, так как $$$1 \oplus 1 < 2 \oplus 0$$$.

Во втором наборе входных данных мы можем взять элементы с индексами $$$1$$$, $$$2$$$ и $$$4$$$ (в $$$0$$$ нумерации). Для них выполняется: $$$2 \oplus 2 < 4 \oplus 1$$$ и $$$4 \oplus 4 < 1 \oplus 2$$$.