만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

로봇융합관 건설

시간 제한2초메모리 제한1024 MB

요약
N개의 칸과 M층이 주어질 때, 파란 블록으로 한 층이나 한 기둥을 모두 채우는 게임에서 민재가 선공과 후공 중 무엇을 골라야 하는지 구합니다.
난이도

보통10점 중 6점

유형
게임 이론, 수학
정답자
아직 제출이 없습니다

문제

준혁이와 함께 고려대학교 로봇융합관에 가던 민재는 문득 의문이 들어 준혁이와 다음과 같은 대화를 나눴다.

  • 민재: 로봇융합관은 왜 이름이 로봇융합관이에요?
  • 준혁: 그거 로봇이 건물을 지어서 그럴걸?
  • 민재: 와, 진짜요?

이 이야기를 들은 알고리즘 마니아 민재는 로봇융합관 건설에 어떤 건축 알고리즘이 쓰였는지 궁금해졌다. 그래서 준혁 선배를 찾아가 사용된 알고리즘을 알려달라고 부탁했다. 그러자 준혁이는 다음 게임에서 자신을 이기면 알고리즘을 가르쳐주겠다고 했다.

  1. 땅에 1×N1\times N 모양의 직사각형이 그려져 있다. 직사각형은 같은 크기의 이웃한 1×11\times 1 정사각형 NN개로 나뉘어 있으며, 왼쪽부터 순서대로 1부터 NN까지의 수가 쓰여 있다.
  2. 두 사람이 순서를 번갈아 가며 크기 1의 정육면체 블록을 하나씩 쌓는다. 블록은 정사각형 NN개의 위치 중 하나에 쌓을 수 있다. 놓으려는 위치에 이미 블록이 쌓여 있다면 그 위에 쌓는다. 단, 로봇융합관은 MM층까지 있으므로 쌓인 블록의 높이는 MM을 넘을 수 없다.
  3. 선공은 항상 파란색 정육면체 블록을 쌓고, 후공은 항상 빨간색 정육면체 블록을 쌓는다.
  4. N×MN\times M개의 정육면체 블록이 모두 쌓이는 순간 게임이 끝난다. 게임이 끝난 후, 가로 방향 한 줄이 모두 파란색이거나 세로 방향 한 줄이 모두 파란색인 줄이 존재하면 선공이 이기고, 존재하지 않으면 후공이 이긴다.

준혁이는 민재에게 선공과 후공을 고를 권리를 양보했다. 다만 깐깐한 준혁이는 TT개의 게임을 각각 독립적으로 진행하고, 모든 게임에서 민재가 이겨야만 알고리즘을 알려주겠다고 했다. 각 게임마다 NN과 MM이 주어졌을 때, 민재가 이기려면 선공과 후공 중 무엇을 골라야 하는지 구하라. 두 사람 모두 게임을 잘하여 항상 최적으로 진행한다고 가정한다.

입력

첫 줄에 게임의 횟수를 나타내는 정수 T(1≤T≤106)T(1 \leq T \leq 10^6)이 주어진다.

다음 줄부터 TT개의 줄에 걸쳐 각 게임의 조건을 나타내는 두 정수 N(1≤N≤1018)N(1 \leq N \leq 10^{18})과 M(1≤M≤1018)M(1 \leq M \leq 10^{18})이 공백을 사이에 두고 주어진다.

출력

각 게임마다 주어진 조건에서 민재가 선공과 후공 중 무엇을 골라야 하는지 한 줄에 출력한다. KK번째 줄에는 KK번째 게임의 답을 출력한다.

선공을 골라야 하면 First를, 후공을 골라야 하면 Second를 출력한다.

힌트

로봇융합관의 건물 공사는 실제로 로봇이 담당했으며, 문제에 제시된 게임은 실제 로봇융합관 건설과는 무관하다.

예제1

  1. 예제 1

    입력
    3
    1 3
    2 6
    4 6
    
    예상 출력
    First
    First
    Second