1차원 돌 게임 2

이 문제는 1차원 돌 게임 1과 굵은 글씨로 적힌 부분만 다릅니다.

동우와 재우는 $1\times n$ 모양의 직선형 격자판에서 처음에 한 칸에 한 개씩 돌을 올려 둔 상태로 게임을 진행하려 한다.

게임은 동우부터 시작해 턴을 번갈아 가면서 돌을 가져간다. 즉, 동우는 홀수 번째 턴에, 재우는 짝수 번째 턴에 진행한다.

• 첫 번째 턴에는 $1$개의 칸을 골라 그곳에 놓인 돌을 가져간다.
• 두 번째 턴부터는 직전 턴에 상대방이 가져간 돌의 개수가 $x$개라면, $1$ 이상 $x+1$ 이하의 정수 $y$를 하나 골라서, 돌이 놓여져 있는 연속한 $y$개의 칸을 골라 그 영역에 놓인 모든 돌을 가져간다.
• 돌을 가져갈 때마다, 돌을 가져간 칸(들)을 기준으로 남은 돌들이 두 부분으로 나누어진다면, 놓인 돌의 개수가 더 적은 부분에 놓인 돌을 모두 버린다. 두 부분에 놓인 돌의 개수가 같다면 한 부분을 선택해 놓인 돌을 모두 버린다. 두 부분으로 나누어지지 않고 한 부분만 있는 경우 버리지 않는다.
• 자신의 턴에 조건에 맞게 돌을 가져가지 못한다면 그 사람이 패배하며, 상대방이 승리한다.

둘 다 승리하기 위해 최선의 플레이를 한다면 누가 이기는지 출력하시오.

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

각 테스트 케이스별로 한 줄에 하나씩 초기의 돌의 개수 $n$이 주어진다. $(1\le n\le 10^{18})$

같은 $n$이 여러 번 주어지지 않는다.

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