Game on Mars
In the year 2020, Alice and Bob will land on Mars just to play a game that will be broadcasted live for the humans on earth. The game is described below:
There will be a 2-Dimensional grid. The columns of this grid are numbered from left to right starting with index 1 and rows are number from top to bottom starting with index 1. There are N coins. Each coin is placed exactly on one cell of the grid. Each cell may contain zero, one or multiple coins. In each turn, one can perform one of the following moves:
i. Take away any single coin from the grid permanently. (always applicable for the coins which are present on the grid.)
ii. Take away any single coin from its current location and put it back to any cell on the left of its current location of the same row. (not applicable for the coins which are on the 1st column)
iii. Take away any single coin from its current location and put it back to any cell on the up of its current location of the same column. (not applicable for the coins which are on the 1st row)
Alice and Bob will turn alternatively. Both of them will play optimally to win the game. Alice will move first. The person who will make the last move will be the winner of the game. Now, you have to determine who will win the game. If Alice is the winner, you have to calculate how many ways she can perform her first move that leads the game to her winning.
First line of inputs contains the number of test case T (1 ≤ T ≤ 100). In the first line of each test case, given the value of N, (1≤ N ≤ 10000) and next N lines will describe the location of each coin as (x, y) on the gird where x is the row number and y is the column number of the coin. (1≤ x, y ≤ 109)
For each test case, output a single line like “Case X: Y” without the quotes where X is the test case number and Y is the name of the winner. If Alice wins the game, print the number of ways Alice can perform her first move, in the next line.
For more understanding, please look at the format of inputs and outputs below.
2 2 1 2 2 1 2 1 1 2 1
Case 1: Bob Case 2: Alice 1