Нім
Нім - це гра для 2-х гравців з декількома купками камінчиків. Гравці по черзі роблять ходи, забираючи один або декілька камінчиків із однієї купки. Гра завершується коли забрано останній камінчик, і гравець, який його забрав, оголошується переможцем. Враховуючи задану позицію у грі Нім, Ваше завдання полягає у знаходженні кількості виграшних у ній ходів.
Позиція в Нім називається "програшною", якщо після довільного ходу першого гравця він в результаті програє, при умові, що обидва гравці дотримуються найкращої стратегії. А "виграшний хід" - це хід, після якого для другого гравця позиція стає програшною. Існує знаменита теорема, яка класифікує всі проиграшні позиції. Припустимо, у деякій позиції гри Нім задано n купок, які містять відповідно k_1, k_2, …, k_n камінчиків; у такій позиції існує всього k_1 + k_2 + … + k_n можливих ходів. Запишемо всі задані значення k_i у двійковій системі числення (системі з основою 2). Позиція Нім є програшною тоді і лише тоді, коли у такому запису k_i, кількість одиниць у кожному розряді парна. Іншими словами, позиція програшна тоді і лише тоді, коли виключне "АБО" (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, є ознакою закінчення вхідних даних і не повинен опрацьовуватись.
Вихідні дані
Для кожного заданого тесту вивести в окремому рядку кількість виграшних для даної позиції ходів.