CS: The Kangaroo Hops For Two

There is a two-player game on $M \times N$ board ( $M$ rows, $N$ columns), with the following rules:

1. At the start of the game, a kangaroo game piece is placed on the bottom left square of the board.

2. Players alternate turns moving the kangaroo, and the first player moves first.

3. On the player's turn, they can either move the kangaroo some number of squares to the right, keep​ it in the same row, or they can move it to the leftmost square on the row above.

4. A player loses if they are unable to make a move.

Mio and Mai decided to play this game. Mio wants to know whether she can win a game before it even starts, if they play optimally, of course. After all, Mai is prone to cheating, so don't worry You are helping the good side.

You will be given a file, where in the first row there will be a number $G$ representing how many games they will be playing. In the following $G$ lines, there will be $3$ numbers, for $i^\text{th}$ row those will be $M_i$ , $N_i$ and $P_i$ , in that order. $M_i$ and $N_i$ represent the board size for $i^\text{th}$ game. The $P_i$ is information on who is the first player for $i^\text{th}$ game. For $P_i = 0$ Mai plays first, whilst for $P_i = 1$ Mio plays first.

For the $G$ described games, you need to answer how many wins will Mio have.

Click for FILE .

Guarantees:

• For every $i$ : $P_i \in \{ 0, 1 \}$ .
• For every $i$ : $1 \le M_i , N_i < 2^{32}$ .

Inspiration .

If there are questions for this problem, ask here .