GAME2 - Looks like Nim - but it is not

no tags 

Goran and Stjepan play an interesting game. On the table between them, there is a sequence of N skyscrapers made of Lego bricks. All of them are made of equal bricks and each of them has a height, which equals the number of bricks in it.

Goran plays first; then Stjepan, then Goran, then Stjepan and so on. In each move, a player has to find the highest skyscraper in the sequence (if there's more than one, he chooses any of them) and reduces its height - that is, takes away an arbitrary (positive) number of bricks from it.

The winner of the game is the one who takes away the last brick. Equivalently, the loser of the game is the one who is not able to make a move.

Help Goran and tell him in how many ways he can play his first move, so that he can certainly win (no matter how Stjepan played). If Goran doesn't have a winning strategy at all, the number of ways is zero.

Input

In the first line of input, there is an integer T ≤ 3, the number of test cases.

Then follow T blocks, each of them in two lines:

  • N ≤ 300 000, the number of skyscrapers in the sequence.

  • a sequence of N integers in the range [0, 106].

Output

For each of the T games, print the required number of ways.

Example

Input:
3
5
0 1 0 1 0
3
0 7 0
5
1 0 1 0 1

Output:
0
1
3

hide comments
Adrian Satja Kurdija: 2011-09-14 09:34:38

@Sidhart Gupta: number of different sets of bricks.

Sidharth Gupta: 2011-09-14 09:34:38

My code while running shows "running judge(7)" and then WA :(
can some one tell me where my code fails?? Submission id: 5300732

The number of ways means the no. of skyscrapers from which he can make a move or the no. of different set of bricks he can pick up initially from highest skyscrapers to ensure his win??

Last edit: 2011-06-27 12:13:05
.::Manish Kumar::.: 2011-09-14 09:34:38

Answer fits in long long (if u were wondering)

~ adieus ~: 2011-09-14 09:34:38

@Mark - We Indians discovered it for a purpose :P !

Adrian Satja Kurdija: 2011-09-14 09:34:38

@Mark: right, there is no point of zero sized towers in the input, but zero is always a good friend. And if all towers are 0, output is 0 since the first player cannot make a move so he loses.

Mark Gordon: 2011-09-14 09:34:38

What is the point of the zero sized towers in the input? Also it's unclear what the output is if all the towers are 0.

The Raven: 2011-09-14 09:34:38

Blank lines between test cases aren't needed in the output if you were wondering.

Last edit: 2011-04-14 23:31:12

Added by:Adrian Satja Kurdija
Date:2011-04-13
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:idea of Goran Zuzic