33475번 - 정점들을 모두 연결하면 위험한 이유는? 서브태스크

문제

다이어서

MatKor의 2022년 2학기 프로젝트는 머신러닝, 게임, 시뮬레이션, 알고리즘, 대회 개최, 웹 프로젝트로 6개가 있었다. 이 중 창호가 주도한 게임 프로젝트는 간단한 물리 엔진을 만들고, 이를 이용해 게임을 만드는 프로젝트였다.

유학을 준비하던 당시 MatKor의 회장 창호는 예훈이에게 게임 프로젝트에서 만들만한 게임이 있을지 물어봤다. 하지만 알고리즘에 뇌가 잠식당한 예훈이는 ‘게임’이라는 단어를 알고리즘에서 말하는 ‘게임’ 이론으로 이해했다. 예훈이는 자신이 이해한 ‘게임’ 이론을 기준으로 새로운 게임을 제시했다.

동우와 재우는 $N$개의 정점을 가지고 게임을 한다. 초기에는 그려진 간선이 없으며, 다음과 같이 게임이 진행된다.

• 게임 시작 전 $P=0$ 혹은 $P=1$을 정하며, $P$의 값은 두 명 모두 알고 있다.
• 게임의 승패는 $P$에 따라 다음과 같이 결정된다.
  • $P=0$인 경우 자신이 차례를 시작할 때 모든 정점이 연결되어 있는 상태가 주어지는 경우 해당 플레이어가 승리하며, 게임이 종료된다.
  • $P=1$인 경우 자신이 차례를 시작할 때 모든 정점이 연결되어 있는 상태가 주어지는 경우 해당 플레이어가 패배하며, 게임이 종료된다.
• 동우부터 시작하여 차례를 번갈아 가며, 직접 연결되지 않은 서로 다른 두 정점을 골라 직접 연결하는 간선을 그린다.

여기서 모든 정점이 연결되어 있다는 것은 간선을 통해 임의의 두 정점 사이를 이동할 수 있음을 의미하며, 서로 다른 두 정점이 직접 연결되지 않았다는 것은 두 정점을 끝점으로 하는 간선이 없음을 의미한다.

주어진 $N$과 $P$에 대해 동우와 재우가 각자 승리하기 위해 최선으로 행동한다면 누가 승리하는지 구해보자.

당연하지만, 누군가 패배하면 다른 한 명은 승리한다.

입력

첫 번째 줄에 테스트 케이스의 개수 $T(1\le T\le 10^6)$가 주어진다.

각 테스트 케이스 별로 한 줄에 $N(1\le N\le 10^{18}),ドル $P(P\in\{0,1\})$가 공백으로 구분되어 주어진다.

출력

각 테스트 케이스에 대해 동우가 승리하면 kidw0124를, 재우가 승리하면 eoaud0108을 한 줄에 하나씩 출력한다.

제한

서브태스크

힌트