B. Одиссея Хамона
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Джонатан сражается с приспешниками-вампирами DIO. Всего их $$$n$$$, а их силы равны $$$a_1, a_2, \dots, a_n$$$. $$$\def\and {{\,\texttt{&}\,}}$$$

Обозначим $$$(l, r)$$$ как группу, состоящую из вампиров с индексами от $$$l$$$ до $$$r$$$. Джонатан понимает, что сила любой такой группы находится в её самом слабом звене, то есть побитовом И. Более формально, уровень силы группы $$$(l, r)$$$ определяется как $$$$$$f(l,r) = a_l \and a_{l+1} \and a_{l+2} \and \ldots \and a_r.$$$$$$ Здесь $$$\and$$$ обозначает операцию побитового И.

Поскольку Джонатан хочет быстро победить вампиров, он разделит вампиров на подряд идущие группы так, чтобы каждый вампир был в ровно одной группе, а сумма сил групп была минимальна. Среди всех подходящих способов разделить вампиров, он хотел бы найти способ с максимальным количеством групп.

Учитывая силы каждого из $$$n$$$ вампиров, найдите максимальное число групп среди всех возможных способов разделить вампиров с наименьшей суммой сил.

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

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

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

Вторая строка каждого набора входных данных содержит $$$n$$$ целых $$$a_1,a_2,\ldots,a_n$$$ ($$$0 \leq a_i \leq 10^9$$$) — силы каждого вампира.

Сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

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

Пример
Входные данные
3
3
1 2 3
5
2 3 1 5 2
4
5 7 12 6
Выходные данные
1
2
1
Примечание

В первом наборе входных данных оптимальным является принятие всех $$$n$$$ вампиров за одну группу. Тогда, $$$f(1,3) = 1 \and 2 \and 3 = 0$$$.

Во втором наборе входных данных оптимальным является создание $$$2$$$ групп, $$$(2,3,1)$$$ и $$$(5,2)$$$. Тогда, $$$f(1,3) + f(4,5) = (2 \and 3 \and 1) + (5 \and 2) = 0 + 0 = 0$$$.