Ним
Ним - это игра для 2-х игроков с несколькими кучками камешков. Игроки по очереди делают ходы, забирая один или несколько камушков из одной кучки. Игра заканчивается когда забран последний камешек, и игрок, забравший его, объявляется победителем. Учитывая заданную позицию в игре Ним, Ваша задача состоит в нахождении количества выигрышных в ней ходов.
Позиция в Ним называется "проигрышной", если после любого хода первого игрока он в результате проигрывает, при условии, что оба игрока придерживаются наилучшей стратегии. А "выигрышный ход" - это ход, после которого для второго игрока позиция становится проигрышной. Существует знаменитая теорема, которая классифицирует все проигрышные позиции. Предположим, в некоторой позиции игры Ним задано n кучек, соответственно содержащих k_1, k_2, …, k_n камешков; из такой позиции существует в точности k_1 + k_2 + … + k_n всевозможных ходов. Запишем все заданные значения k_i в двоичной системе счисления (системе с основанием 2). Позиция Ним является проигрышной тогда и только тогда, когда в такой записи количество единиц в каждом разряде четно. Иными словами, позиция проигрышна тогда и только тогда, когда исключающее "ИЛИ" (xor) по всем кучкам k_i равно 0.
Рассмотрим три кучки, количество камешков в которых соответственно равно k_1 = 7, k_2 = 11, и k_3 = 13. В двоичной записи эти значения имеют такой вид:
11110111101
В этой записи в одном из столбиков присутствует нечетное количество единиц, следовательно эта позиция не проигрышная. Предположим, что мы изменили кучку k_3 до 12 камешков. После этого количество единиц в каждом двоичном разряде стало четным, следовательно такая позиция Ним стала проигрышной. Выигрышным ходом будет любой ход, приводящий к проигрышной для соперника позиции, следовательно для позиции k_1 = 7, k_2 = 11, и k_3 = 13 выигрышным будет любой ход, удаляющий третью единицу в любой из строк последнего столбика двоичной записи чисел. Очевидно, что таких ходов существует всего три, при которых удаляется любая из нечетных единиц в последнем разряде.
Входные данные
Входные данные содержат несколько тестов, каждый из которых начинается со строки, содержащей количество кучек с камешками n (1 ≤ n ≤ 1000). В следующей строке содержится n положительных чисел, 1 ≤ k_i ≤ 1000000000, количество камешков в соответствующей кучке. Строка, содержащая значение n = 0, является признаком окончания входных данных и не должна обрабатываться.
Выходные данные
Для каждого заданного теста вывести в отдельной строке количество выигрышных для данной позиции ходов.