Нім

Обмеження: 2 сек., 256 МіБ

Зеник та Марічка грають в одну відому гру. У них є \(n\) купок камінців, в \(i\)-ій купці \(a_i\) камінців. Відомо, що Марічка може виграти, якщо XOR усіх розмірів купок рівний 0.

Тепер Марічка вирішила змахлювати та додати декілька камінців у купки. Визначте, яку мінімальну кількість камінців потрібно додати Марічці, щоб вона змогла перемогти. Зауважте, що створювати нові купки чи перекладати камінці в наявних купках Марічка не може.

Операція XOR — операція додавання за модулем 2. Для того, щоб знайти XOR двох чисел \(a\) та \(b\), потрібно розкласти обидва числа у двійкову систему та додати за модулем 2 окремо кожен біт. Наприклад, 4 XOR 6 = 2, бо \(4_{10}=100_2\), \(6_{10}=110_2\). \(4_{10}\) XOR \(6_{10}=010_2=2_{10}\). Ця операція реалізована як оператор \(^{\wedge}\) в C++, C#, Java та xor у Pascal. XOR набору чисел \(c_1, c_2, \ldots, c_k\) рівний \((\ldots(( c_1 \mbox{ XOR } c_2) \mbox{ XOR } c_3) \ldots \mbox{ XOR } c_k)\). XOR пустого набору чисел рівний 0.

Вхідні дані

У першому рядку дано ціле число \(n\) — кількість купок.

У другому рядку містяться \(n\) цілих чисел \(a_i\) — початкова кількість камінців в \(i\)-ій купці.

Вихідні дані

У єдиному рядку виведіть ціле число — мінімальну кількість камінців, які необхідно додати Марічці.

Обмеження

\(2 \le n \le 10^3\),

\(0 \le a_i \le 10^9\).

Приклади