님(Nim)

님(Nim)은 여러 개의 돌 더미를 놓고 두 사람이 겨루는 게임입니다. 두 사람은 번갈아 차례를 진행하며, 자기 차례에는 더미 하나를 골라 그 더미에서 돌을 하나 이상 가져갑니다. 모든 돌이 사라지면 게임이 끝나고, 마지막으로 돌을 가져간 사람이 승자가 됩니다. 님의 한 국면이 주어질 때, 그 국면에서 가능한 '이기는 수'가 몇 가지인지 구하세요.

어떤 국면에서 먼저 두는 쪽이, 양쪽 모두 완벽하게 두었을 때 지게 된다면 그 국면을 '지는 국면'이라고 부릅니다. 따라서 '이기는 수'란 두고 난 뒤의 국면을 지는 국면으로 만드는 수를 말합니다. 지는 국면을 모두 분류하는 유명한 정리가 있습니다. 어떤 님 국면에 돌이 각각 $k_1, k_2, \dots, k_n$개인 더미가 $n$개 있다고 하면, 이 국면에서 둘 수 있는 수는 모두 $k_1 + k_2 + \dots + k_n$가지입니다. 각 $k_i$를 이진법(2진수)으로 나타냈을 때, 모든 $k_i$에 대해 각 자릿수마다 1의 개수가 짝수이면, 그리고 오직 그럴 때에만 그 국면은 지는 국면입니다. 다시 말해, $k_i$들의 XOR가 0일 때, 그리고 오직 그때에만 지는 국면입니다.

예를 들어 $k_1 = 7$, $k_2 = 11$, $k_3 = 13$인 세 더미 국면을 생각해 봅시다. 이 값들을 이진수로 쓰면 다음과 같습니다.

• 111
• 1011
• 1101

가장 오른쪽 자리에는 1이 홀수 개 있으므로 이 국면은 지는 국면이 아닙니다. 그런데 만약 $k_3$을 12로 바꾸면 모든 자리마다 1이 정확히 두 개씩 있게 되어 국면이 지는 국면이 됩니다. 이기는 수란 국면을 지는 국면으로 만드는 수이므로, $k_1 = 7$, $k_2 = 11$, $k_3 = 13$일 때 세 번째 더미에서 돌 하나를 가져가는 것은 이기는 수입니다. 실제로 이 국면에서 이기는 수는 정확히 세 가지로, 세 더미 각각에서 돌 하나씩을 가져가는 수입니다.

입력은 여러 개의 테스트 케이스로 이루어집니다. 각 테스트 케이스는 더미의 개수 $n$ ($1 \le n \le 1000$)이 적힌 줄로 시작합니다. 다음 줄에는 각 더미의 돌 개수를 나타내는 $n$개의 양의 정수 $k_i$ ($1 \le k_i \le 1{,}000{,}000{,}000$)가 주어집니다. 입력의 끝은 $n = 0$인 테스트 케이스로 표시되며, 이 케이스는 처리하지 않습니다.

각 테스트 케이스마다 주어진 님 국면에서 이기는 수의 개수를 정수 하나로 한 줄에 출력하세요.