A. Игра в Ним это игра в XOR
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Алиса и Боб играют в игру с массивом $$$a$$$, состоящим из $$$n$$$ целых неотрицательных чисел. Алиса ходит первой.

В каждый ход текущий игрок должен выбрать массив из $$$n$$$ неотрицательных целых чисел $$$b = [b_1, b_2, \ldots, b_n]$$$, удовлетворяющий следующим условиям:

  1. $$$0 \le b_i \le a_i$$$ для всех $$$1 \le i \le n$$$;
  2. $$$\sum_{i=1}^n b_i \gt 0$$$ (то есть массив $$$b$$$ не состоит целиком из нулей);
  3. $$$b_1 \oplus b_2 \oplus \ldots \oplus b_n = 0$$$, где $$$\oplus$$$ обозначает операцию побитового XOR.

После выбора массива $$$b$$$ игрок обновляет массив $$$a$$$, выполняя $$$a_i \leftarrow a_i - b_i$$$ для всех $$$1 \le i \le n$$$.

Игрок, который не может выполнить такую операцию, проигрывает.

Определите количество допустимых выборов массива $$$b$$$, которые Алиса может сделать в первый ход, гарантируя победу при условии, что оба игрока играют оптимально. Так как это число может быть большим, выведите ответ по модулю $$$998\,244\,353$$$.

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

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

Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$1 \le n \le 10^6$$$) — длину массива $$$a$$$.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \lt 2^{30}$$$) — элементы массива $$$a$$$.

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

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

Для каждого набора входных данных выведите количество допустимых выборов массива $$$b$$$, которые Алиса может сделать в первый ход, гарантируя победу, по модулю $$$998\,244\,353$$$.

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

В первом наборе входных данных Алиса должна выбрать массив $$$b$$$ длины $$$1$$$. Условия требуют $$$b_1 \le a_1$$$, $$$b_1 \gt 0$$$ и $$$b_1 = 0$$$. Невозможно одновременно выполнить $$$b_1 \gt 0$$$ и $$$b_1 = 0$$$. Таким образом, у Алисы нет допустимых ходов, и она сразу проигрывает. Ответ равен $$$0$$$.

Во втором наборе входных данных $$$a = [1, 2]$$$. Алиса должна выбрать $$$b = [b_1, b_2]$$$. Условие $$$b_1 \oplus b_2 = 0$$$ означает, что $$$b_1 = b_2$$$. Поскольку $$$0 \le b_1 \le 1$$$ и $$$0 \le b_2 \le 2$$$, а массив $$$b$$$ не может состоять целиком из нулей, единственный допустимый выбор — $$$b = [1, 1]$$$. Если Алиса выбирает $$$b = [1, 1]$$$, массив обновляется до $$$a = [1-1, 2-1] = [0, 1]$$$. Теперь ход Боба. Аналогично ситуации Алисы, Боб должен выбрать $$$b'$$$ такой, что $$$b'_1 = b'_2$$$. Так как $$$a_1 = 0$$$, он вынужден выбрать $$$b'_1 = 0$$$, что означает $$$b'_2 = 0$$$. Поскольку допустимый ход требует $$$\sum b'_i \gt 0$$$, у Боба нет допустимых ходов, и он проигрывает. Следовательно, $$$b = [1, 1]$$$ — выигрышный ход для Алисы, и ответ равен $$$1$$$.