Two HackerRank staffers found a secret room with a mysterious square board and decided to play a game with it. The game has the following rules:
At the beginning of the game, the players write a single digit (given as input) ranging from to in each cell composing the square board.
The players move in alternating turns. In each move, the current player performs the following actions:
Chooses a board that has at least one non-prime number written on it and has more than one cell (i.e., dimensions ).
Cuts the chosen board into smaller boards by breaking it along any horizontal or vertical line at the edge of a cell.
Note: Although the game starts with one board, that board is split in two during each move. At the beginning of the move, a player can choose any one of the pieces of the original board (as long as it can have a legal move performed on it).
The game ends when there are no more cuttable boards (i.e., there are boards, or all boards have only prime numbers written on them). The first player who is unable to make a move loses.
Given the value of and the respective numbers written in each cell of the board, determine whether the person who wins the game is the first or second person to move. Assume both players move optimally.