We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Game Theory
  4. Chessboard Game, Again!

Chessboard Game, Again!

Problem
Submissions
Leaderboard
Discussions
Editorial

Two players are playing a game on a chessboard. The rules of the game are as follows:

  • The game starts with coins located at one or more coordinates on the board (a single cell may contain more than one coin). The coordinate of the upper left cell is , and the coordinate of the lower right cell is .
  • In each move, a player must move a single coin from some cell to one of the following locations:

    1. .

    Note: The coin must remain inside the confines of the board.

  • The players move in alternating turns. The first player who is unable to make a move loses the game.

The figure below shows all four possible moves:

chess

Note: While the figure shows a board, this game is played on a board.

Given the value of and the initial coordinate(s) of coins, determine which player will win the game. Assume both players always move optimally.

Input Format

The first line contains an integer, , denoting the number of test cases.
Each test case is defined as follows over the subsequent lines:

  1. The first line contains an integer, , denoting the number of coins on the board.
  2. Each line (where ) of the subsequent lines contains space-separated integers describing the respective values of and of the coordinate where coin is located.

Note: Recall that a cell can have more than one coin (i.e., any cell can have to coins in it at any given time).

Constraints

  • , where .

Output Format

On a new line for each test case, print if the first player is the winner; otherwise, print .

Sample Input

2
3
5 4
5 8
8 2
6
7 1
7 2
7 3
7 4
7 4
7 4

Sample Output

First
Second

Author

Shafaet

Difficulty

Medium

Max Score

30

Submitted By

1758

Need Help?


View discussions
View editorial
View top submissions

rate this challenge

MORE DETAILS

Download problem statement
Download sample test cases
Suggest Edits
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy