E. Рудольф и коктейли
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Рудольф решил немного сменить обстановку и пойти поработать барменом. Естественно он беспокоится о своих клиентах и хочет сделать ассортимент коктейлей разнообразным.

Всего у него на полке имеется $$$n$$$ ингредиентов, расположенных в ряд. Рудольф, применив свои математические способности, рассчитал, что вкусность $$$i$$$-го ингредиента равна $$$a_i$$$. Исходя из этого, он определяет вкусность коктейля как побитовое исключающее ИЛИ вкусностей входящих в него ингредиентов.

Помогите Рудольфу определить, сколько коктейлей различных вкусностей он сможет изготовить. В целях экономии скорости изготовления коктейлей Рудольф решил брать с полки только последовательные ингредиенты.

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

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

Далее следуют описания наборов.

Первая строка набора содержит целое число $$$n$$$ ($$$1 \le n \le 10^4$$$) — количество ингредиентов для коктейлей.

Вторая строка набора содержит $$$n$$$ целых чисел $$$a_i$$$ ($$$1 \le i \le n, 0 \le a_i \lt 2^{10}$$$) — вкусности ингредиентов в том порядке, в котором они расположены на полке.

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

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

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

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

В первом тесткейсе мы можем получить $$$7$$$ различных значений вкусностей:

  • $$$0$$$ — взяв ингредиенты со $$$2$$$-го по $$$5$$$-й;
  • $$$1$$$ — взяв ингредиент номер $$$3$$$;
  • $$$2$$$ — взяв ингредиенты с $$$4$$$-го по $$$5$$$-й;
  • $$$3$$$ — взяв ингредиенты с $$$3$$$-го по $$$5$$$-й;
  • $$$8$$$ — взяв ингредиент номер $$$5$$$;
  • $$$10$$$ — взяв ингредиент номер $$$4$$$;
  • $$$11$$$ — взяв ингредиенты с $$$3$$$-го по $$$4$$$-й.

Во втором тесткейсе мы можем получить $$$6$$$ различных значений вкусностей:

  • $$$1$$$ — взяв ингредиент номер $$$1$$$;
  • $$$4$$$ — взяв ингредиент номер $$$2$$$;
  • $$$5$$$ — взяв ингредиенты с $$$1$$$-го по $$$2$$$-й;
  • $$$8$$$ — взяв ингредиент номер $$$3$$$;
  • $$$12$$$ — взяв ингредиенты со $$$2$$$-го по $$$3$$$-й;
  • $$$13$$$ — взяв ингредиенты с $$$1$$$-го по $$$3$$$-й.