{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cspan lang\u003d\"en-us\"\u003e\u003cp\u003eNim is a 2-player game featuring several piles of stones. Players alternate turns, and on his/her turn, a player’s move consists of removing \u003ci\u003eone or more stones\u003c/i\u003e from any single pile. Play ends when all the stones have been removed, at which point the last player to have moved is declared the winner. Given a position in Nim, your task is to determine how many winning moves there are in that position.\u003c/p\u003e\u003cp\u003eA position in Nim is called “losing” if the first player to move from that position would lose if both sides played perfectly. A “winning move,” then, is a move that leaves the game in a losing position. There is a famous theorem that classifies all losing positions. Suppose a Nim position contains \u003ci\u003en\u003c/i\u003e piles having \u003ci\u003ek\u003c/i\u003e\u003csub\u003e1\u003c/sub\u003e, \u003ci\u003ek\u003c/i\u003e\u003csub\u003e2\u003c/sub\u003e, …, \u003ci\u003ek\u003csub\u003en\u003c/sub\u003e\u003c/i\u003e stones respectively; in such a position, there are \u003ci\u003ek\u003c/i\u003e\u003csub\u003e1\u003c/sub\u003e + \u003ci\u003ek\u003c/i\u003e\u003csub\u003e2\u003c/sub\u003e + … + \u003ci\u003ek\u003csub\u003en\u003c/sub\u003e\u003c/i\u003e possible moves. We write each \u003ci\u003ek\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e in binary (base 2). Then, the Nim position is losing if and only if, among all the \u003ci\u003ek\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e’s, there are an even number of 1’s in each digit position. In other words, the Nim position is losing if and only if the \u003ci\u003exor\u003c/i\u003e of the \u003ci\u003ek\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e’s is 0.\u003c/p\u003e\u003cp\u003eConsider the position with three piles given by \u003ci\u003ek\u003c/i\u003e\u003csub\u003e1\u003c/sub\u003e \u003d 7, \u003ci\u003ek\u003c/i\u003e\u003csub\u003e2\u003c/sub\u003e \u003d 11, and \u003ci\u003ek\u003c/i\u003e\u003csub\u003e3\u003c/sub\u003e \u003d 13. In binary, these values are as follows:\u003c/p\u003e\u003cdiv align\u003d\"center\"\u003e\u003cpre\u003e 111\u003cbr\u003e1011\u003cbr\u003e1101\u003cbr\u003e \u003c/pre\u003e\u003c/div\u003e\u003cp\u003eThere are an odd number of 1’s among the rightmost digits, so this position is not losing. However, suppose \u003ci\u003ek\u003c/i\u003e\u003csub\u003e3\u003c/sub\u003e were changed to be 12. Then, there would be exactly two 1’s in each digit position, and thus, the Nim position would become losing. Since a winning move is any move that leaves the game in a losing position, it follows that removing one stone from the third pile is a winning move when \u003ci\u003ek\u003c/i\u003e\u003csub\u003e1\u003c/sub\u003e \u003d 7, \u003ci\u003ek\u003c/i\u003e\u003csub\u003e2\u003c/sub\u003e \u003d 11, and \u003ci\u003ek\u003c/i\u003e\u003csub\u003e3\u003c/sub\u003e \u003d 13. In fact, there are exactly three winning moves from this position: namely removing one stone from any of the three piles.\u003c/p\u003e\u003c/span\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cspan lang\u003d\"en-us\"\u003e\u003cp\u003eThe input test file will contain multiple test cases, each of which begins with a line indicating the number of piles, 1 ≤ \u003ci\u003en\u003c/i\u003e ≤ 1000. On the next line, there are n positive integers, 1 ≤ \u003ci\u003ek\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e ≤ 1, 000, 000, 000, indicating the number of stones in each pile. The end-of-file is marked by a test case with \u003ci\u003en\u003c/i\u003e \u003d 0 and should not be processed.\u003c/p\u003e\u003c/span\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eFor each test case, write a single line with an integer indicating the number of winning moves from the given Nim position.\u003c/p\u003e"}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\r\n7 11 13\r\n2\r\n1000000000 1000000000\r\n0\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\r\n0\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}